模除法期间整数溢出

Question

我正在尝试计算以下值。

prod = 1;
for(int i=1;i<N;i++){
    prod = prod*i;
}

由于 N 可能很大，我被要求计算模数 10^9+7，我做到了。

int prod =1;    
for(int i=1;i<N;i++)
{
    prod = ((prod%1000000007) * (i%1000000007))%1000000007;     
}

有人做了。

long ways=1;    
for(int j=1;j<N;j++)
{
    ways = (int)(j * ways % 1000000007);    
}

网上判断第二个正确。为什么会这样？

所以我运行这个

int prod = 1;
long ways = 1;

for(int j=1;j<14;j++){
     prod = ((prod%1000000007) * (j%1000000007))%1000000007;

     ways = (int)(j * ways % 1000000007);

     if(prod!=ways){

            System.out.println(prod+" "+ways);
            System.exit(0);
        }
     System.out.println(prod+" "+ways+" "+j);
}

并且当 prod or ways 是 479001600 并且 j 是 12 在下一次迭代中它们不相等。两者都小于 int max 即 2147483647

所以我这样做，他们是平等的

 prod = ((479001600%1000000007) * (12%1000000007))%1000000007;

         ways = (int)(12 * 479001600 % 1000000007);

         if(prod!=ways){

                System.out.println(prod+" "+ways);
                System.exit(0);
            }
         System.out.println(prod+" "+ways);

我认为这是铸造的东西。但是想不通。如果我做错了什么请告诉我？

Answer 1

转换不是问题，但将 prod 更改为 long 的数据类型将解决您的问题。这样做的原因是当 j=13 时乘法会溢出，即使你随后对结果取模也是如此。

Answer 2

有一段时间没做 Java，但这似乎与语言无关（与模数无关）：您使用的是 int (prod)，另一个解决方案使用 long (ways).

您的变量（prod 或 ways）与 j（此处为 12）的乘法溢出。 479001600 * 12 是 5,748,019,200。如果两个参数都是 int 这将溢出。最大的32位值为4,294,967,295.

如果表达式的一侧是长整数，则结果将是长整数 -> 不会溢出。

模除法期间整数溢出

Integer overflow during modulo division

java

modulo