乘法時溢出

我想計算（N * N *（N + 1）/ 2）mod M的值，其中N可以達到10^18，M最大達到10^7。我試圖編寫它，但不知道它爲什麼會溢出的原因。這裏是我的代碼：乘法時溢出

在主我做這樣的事情：

long long tt=mulmod(N,N+1,MOD)*InverseEuler(2,MOD); 
long long mm=mulmod(tt,N,MOD);

而且mulmod功能查找（A * B）％C。這是因爲如下：

long long mulmod(long long a,long long b,long long c) 
{  
    long long x = 0,y = a%c; 
    while(b > 0) 
    { 
     if(b%2 == 1) 
     { 
      x = (x+y)%c; 
     } 
     y = (y*2)%c; 
     b /= 2; 
    } 
    return x%c; 
}

而且逆歐拉是這樣的：

long long p(long long n,int m,long long int MOD) 
{ 
    if(m == 0) return 1%MOD; 

    long long x = p(n,m/2,MOD); 
    if(m%2 == 0) 
     return (x*x)%MOD; 
    else 
     return (((x*x)%MOD)*n)%MOD; 
} 
long long InverseEuler(int n,int MOD) 
{ 
    return p(n,MOD-2,MOD); 
}

請幫我在此代碼中發現的錯誤。

來源

2015-02-07 user3840069

你真的需要'mulmod'嗎？當'M'高達10^7時，'（（N％M）*（N％M））％M *（（N + 1）％M）'不會溢出。 – justanothercoder 2015-02-07 04:06:40

@justanothercoder divis by 2怎麼樣？ – user3840069 2015-02-07 04:08:54

@justanothercoder您正在尋找N * N *（N + 1）。對？ – user3840069 2015-02-07 04:12:06

問題是，如果提供了正確的（或錯誤的）操作數集合，每個操作都會溢出。

justanothercode已經暗示在模10^7不會溢出一個漫長的（事實上，它不會溢出長）

您需要使用的身份，註釋

(a+b)%c == ((a%c) + (b%c))%c
(a*b)%c == ((a%c)*(b%c))%c

這些身份的數學證明是微不足道的。

如果值a和b接近long long所能表示的範圍，那麼將它們相加或相乘可能會溢出。但是，這些身份的右側表達式使用模運算符來避免可能溢出的加法或乘法。

無需使用循環。

來源

2015-02-07 10:46:27 Rob

回答

相關問題