c++ - 即使 int 被 10^9+7 模数也会溢出

Question

我为数字的阶乘编写了以下代码:

long int fac[max+1];
    fac[0]=1;


    for(int j=1;j<=max;j++)
        {
            fac[j]=(fac[j-1]*j)%1000000007;
        }


    //Printing
    for(int i=0;i<T;i++)
        {
            cout<<fac[N[i]]<<"\n";
        }

这对 long int 非常有效，但是如果我们将数组更改为 int，我们会得到错误的答案。

请告诉我为什么当 int 的范围大于 10^9+7 时会发生这种情况。

Answer 1

我们知道 0 ≤ fac[j - 1] < 10⁹ + 7。但是 fac[j - 1] * j将比它大 j 倍，而 long 偶尔只有 32 位长 (Windows)。一个 32 位数字可以容纳的绝对最大值是 4294967295，大约只有模数的四倍。

考虑使用 unsigned long long 而不是 long int - 这应该可以工作到 j > 2³⁴。

事实上，鉴于 (a * b) % N 是 mathematically equivalent到 (a % N) * (b % N)，一旦您将 long int 替换为 unsigned long long 你可以重写

fac[j] = (fac[j - 1] * j) % 1000000007

到

fac[j] = (fac[j - 1] * (j % 1000000007)) % 1000000007

然后，因为 1000000007² < 2⁶⁴，你应该能够永远继续这个(尽管你最终会用完 fac，当然)。