java - 模除法期间整数溢出

Question

这个问题已经有答案了:

Need help in mod 1000000007 questions (4 个回答)

已关闭 6 年前。

我正在尝试计算以下值。

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

有一段时间没有接触过 Java，但这似乎与语言无关(并且与模数无关):您正在使用 int (prod)，另一个解决方案使用 long ( >方式)。

变量(prod 或 ways)与 j(此处为 12)的乘法就是溢出。 479001600 * 12 为 5,748,019,200。如果两个参数都是 int，则会溢出。最大的 32 位值为 4,294,967,295。

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