如何计算 (A*B*C)%10000007 其中 A,B,C 最大为 10^18
问问题
677 次
1 回答
2
令 I = 10000007，所以
- A = n1 * I + X1
- B = n2 * I + X2
- C = n3 * I + X3
A * B => (n1 * I + X1) (n2 * I + X2) => n1 * n2 * I^2 + n1 * X2 * I + n2 * X1 * I + X1 * X2 只有 X1 * X2 可以t 除以我
因此，A * B % I === X1 * X2 % I === (A % I) * (B % I) % I
因此 (A * B * C) % I === [(A % I) * (B % I) % I] * (C % I) % I
于 2013-01-07T04:11:37.080 回答