java - 大数模n的快速乘法

Question

可能重复：
在 mod 1000000007 问题中需要帮助

我有一组数字，我想计算总乘积模 1000007。例如，如果我的数组包含 1000 个数字，那么我需要计算以下内容。

int product = 1;
for(int i=0;i<Array_Max;i++)
  product = product * Array[i]

然后产品模 1000007 = ？

是否有任何算法可以优化上述伪代码？现在由于溢出，我无法存储产品。

任何建议表示赞赏。

Answer 1

使用longs 作为产品 - 这足以保存两个整数相乘的结果。

您还需要计算每次迭代的模数，以避免溢出（从数学角度来看，这样做是安全的，因为它不会在最后改变模数 1000007 的结果）。

如果你愿意，你也可以使用BigIntegers，但它会慢得多。