예 : A = 10 ^ 17, B = 10 ^ 17, C = 10 ^ 18.
제품 A * B가 long long int의 한계를 초과합니다.
또한 ((A % C) * (B % C)) % C를 쓰는 것은 도움이되지 않습니다.
64 비트 정수 연산을 유지하고 싶다고 가정하면 이진 긴 나눗셈을 사용할 수 있습니다.이 방법은 여러 덧셈과 두 연산을 곱하는 것으로 요약됩니다. 즉, 이러한 연산자의 오버플로 방지 버전도 필요하지만 비교적 간단합니다.
다음은 A와 B가 이미 양수이고 M보다 작다고 가정하는 Java 코드입니다. 그렇지 않은 경우 미리 쉽게 만들 수 있습니다.
// assumes a and b are already less than m
public static long addMod(long a, long b, long m) {
if (a + b < 0)
return (a - m) + b; // avoid overflow
else if (a + b >= m)
return a + b - m;
else
return a + b;
}
// assumes a and b are already less than m
public static long multiplyMod(long a, long b, long m) {
if (b == 0 || a <= Long.MAX_VALUE / b)
return a * b % m; // a*b > c if and only if a > c/b
// a * b would overflow; binary long division:
long result = 0;
if (a > b) {
long c = b;
b = a;
a = c;
}
while (a > 0) {
if ((a & 1) != 0) {
result = addMod(result, b, m);
}
a >>= 1;
// compute b << 1 % m without overflow
b -= m - b; // equivalent to b = 2 * b - m
if (b < 0)
b += m;
}
return result;
}
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다