我有两个整数 x 和 y 假设 x= 10^5 且 y = 10^8 现在我必须将数字相乘并将它们存储在变量 z 中。我不需要确切的值。 z 可以得到对 100000009 取模的答案。我该怎么做？
提前致谢
最佳答案
一般来说，您应该依赖这种关系:
(a * b) % n = (a % n) * (b % n) % n
在这种特殊情况下，它没有多大帮助，因为您的 a和b都小于 n ，但对于更大的 a或b这保证了您需要处理的最大乘法的数量级为 n^2而不是a * b .
在 64 位系统上，您的当前值为 n^2适合 long 内。如果您预计会有更大的值，那么您将需要一个任意精度的数学库，例如 GMP .
关于c++ - c中大数相乘，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12234113/