product — Как рассчитать (A * B)% C для A, B, C & lt; = 10 ^ 18, в C ++?
Например, A = 10 ^ 17, B = 10 ^ 17, C = 10 ^ 18.
Произведение A * B превышает предел long long int.
Кроме того, написание ((A% C) * (B% C))% C не помогает.
Решение
Предполагая, что вы хотите остаться в пределах 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;
}
Другие решения
Ты можешь использовать
-
Многофункциональная арифметическая библиотека GNU
или же
-
Большая целочисленная библиотека C ++
Если вы работаете только с силой 10 чисел, вы можете создать простой класс с 2 членами: основание и степень 10, поэтому A = 10 ^ 17 будет {1, 17}. Реализация сложения, вычитания, умножения и деления очень проста, как и печать.