java - 避免算术溢出

Question

假设您有 2 个正 long 值 a 和 b，它们大于 2^32(并且小于2^63)，以及一个长整数c。 在 java 和/或 c 中，执行诸如此类的操作的最佳方法是什么？

(a*b)%c

同时避免算术溢出。

编辑: c 在 2^34 左右，有时 a 和 b 都在 2^32 和 c 之间...

对于我所处的具体情况，我最终避免使用 BigInteger。事实上，可以知道 a 和 b 的一个除数> (情况并非总是如此)，因此我会使用取模的算术属性来发挥我的优势。

Answer 1

假设一切都是积极的，那么您可以使用以下数学恒等式:

(a*b)%c == ((a%c) * (b%c)) % c

当然，这仍然不能消除溢出的可能性。

完全避免该问题的最简单方法是使用大整数库。