即使 int 是 mod by 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

与 int fac[max+1];、fac[j-1] * j 是 int * int，结果是 int。

如果你溢出，你有 UB，即使没有符号，你也会丢失数据。

与 long int fac[max+1];，则 fac[j-1] * j 是 long int * long int（int -> long int for j）结果为 long int.

Answer 2

我们知道 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⁶⁴，你应该可以永远继续下去（尽管你最终会 [= space 中的 47=] 当然是 fac。

即使 int 是 mod by 10^9+7 也会溢出

Oveflow even when an int is mod by 10^9+7

c++

int

overflow