模數除法中的整數溢出

我在計算下面的值。模數除法中的整數溢出

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

模數除法中的整數溢出

回答

相關問題