c++ - 在c中乘以大数

Question

我有两个整数 x 和 y让我们说 x= 10^5 和 y = 10^8现在我必须将数字相乘并将它们存储在变量 z 中。我不需要确切的值。 z 可以得到模 100000009 的答案。我该怎么做？

提前致谢

Answer 1

一般来说你应该依赖的关系:

(a * b) % n = (a % n) * (b % n) % n

在这种特殊情况下，它没有太大帮助，因为您的 a 和 b 都小于 n，但是对于更大的 a 或 b 这保证您需要处理的最大乘法是 n^2 而不是 a * b.

在 64 位系统上，n^2 的当前值将适合 long。如果您预计会有更大的值，那么您将需要一个任意精度的数学库，例如 GMP .