模数除法中的整数溢出

我在计算下面的值。模数除法中的整数溢出

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;  
}

其他人做了。

网上法官正在采取第二个正确的。为什么？

所以我跑这

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最大值是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);

我认为这是什么东西铸造少。但无法弄清楚。请告诉我，如果我做错了什么？

来源

2016-12-02 WannaBeCoder

搜索int范围，你会看到问题是。 –

为什么downvote。 Dint我尝试了什么？这是一个微不足道的问题吗？ – WannaBeCoder

这是一个微不足道的问题，因为你已经知道整数有溢出。搜索整数溢出很可能会导致对你的问题的回答。 –

有一段时间没有完成Java，但是这似乎与语言无关（并且与模数无关）：您正在使用int（prod），另一个解决方案使用long（ways）。

的倍增您的变量（prod或ways）与j（这里12）是什么溢出。 479001600 * 12是5,748,019,200。如果两个参数都是int，则会溢出。最大的32位值是4,294,967,295。

如果表达式的一边是长整型，则结果将是长整型 - >无溢出。

来源

2016-12-02 14:29:41

请注意，在溢出32位之前，解决方案可能会遇到符号相关的问题（即当然溢出31位）。 Java的基本类型都是有符号的（char除外，但不是用于这种计算），Java没有模运算符，只有*余数*运算符。 –

谢谢@Benjamin Podszun，我错过了，如果一方很长，结果会很长。所以在'ways =（int）（j * ways％1000000007）'中，转换为int是不必要的，应该是'（（j *（ways％1000000007））％1000000007）;'因为long也可以溢出。 – WannaBeCoder

是的，如果将结果重新分配给long，则不需要将其转换为int。我不明白第二个变化：''''''''是前一次迭代的结果，因此（如果我错了，纠正我）总是<1000000007.额外的操作看起来是不必要的。原始代码（无法投射）已经将j乘以总是小于素数的数字。 –

铸造不是问题，但您的数据类型将prod更改为long将解决您的问题。其原因在于，当你以后采取结果的模数时，即使强硬，乘法也会溢出。

来源

2016-12-02 14:28:44

模数除法中的整数溢出

回答

相关问题