例如,A=10^17、B=10^17、C=10^18。
乘积 A*B 超过了 long long int 的限制。
此外,编写 ((A%C)*(B%C))%C 也无济于事。
问问题
3147 次
2 回答
2
您可以使用
GNU 多精度算术库
或者
C++ 大整数库
如果您只使用 10 的幂,您可以创建一个包含 2 个成员的简单类:一个基数和 10 的幂,因此 A=10^17 将是 {1, 17}。实现加减乘除非常容易,打印也是如此。
于 2014-01-03T20:35:22.247 回答
2
假设您希望保持在 64 位整数运算范围内,您可以使用二进制长除法,这归结为一堆加法和乘以两个操作。这意味着您还需要这些运算符的防溢出版本,但这些都相对简单。
下面是一些 Java 代码,它假设 A 和 B 已经是正数并且小于 M。如果不是,很容易事先将它们设置为正数。
// 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;
}
于 2014-01-03T20:44:10.547 回答