計算pow（x，n）％d時的拐角案例

對於上述問題，我已經爲x的正值和負值提出了一個工作代碼。對於大多數情況的答案是正確的，但是代碼在一個角落案例中失敗了，我似乎無法找到問題所在！我錯過了什麼條件：`計算pow（x，n）％d時的拐角案例

int pow(int x, int n, int d) { 
int i=0,rem=1; 
long long l; 
    if(x==0) 
    { 
     return 0; 
    } 
    if(x==1) 
    { 
     return 1; 
    } 
    if(n==0) 
    { 
     return 1; 
    } 
    x=x%d; 
    if(n%2==0||n==0) 
    { 
     l = ((pow(x,n/2,d))*(pow((x),n/2,d)))%d; 
    } 
    else 
    { 
     l = ((x)*(pow(x,(n-1)/2,d))*(pow((x),(n-1)/2,d)))%d; 
    } 
    if(x<0 && n%2!=0) 
    { 
     return d+l; 
    } 
    else 
    { 
     return l; 
    } 
}

` 在該代碼給出錯誤的ANS的情況：

A: 71045970 
B : 41535484 
C : 64735492 
My Output: 12942068 
Actual Output:20805472

來源

2017-06-05 user3767047

除非您在某處聲明'l'，否則此代碼不應編譯。接下來，'＆n == 0'背後的想法是什麼？最後，你的角落案例是什麼？ – sweber

對我來說看起來像是int overflow問題...我正在這樣做'modpow'：[模塊化算法和NTT（有限域DFT）優化]（https://stackoverflow.com/q/18577076/2521214）。在if語句中，我還會感到更安全，更多'（）'括號。 – Spektre

我個人避免使用l作爲變量名稱，原因很明顯 –

這裏是你的簡化版。

int pow(int x, int n, int d) { 
    long long l; 
    if(n==0) 
    { 
     return 1; 
    } 
    if(n%2==0) 
    { 
     l = (long long)pow(x,n/2,d); 
     return (int)((l * l) % (long long)d); 
    } 
    else 
    { 
     //check negative value of x, and make it positive, so that negative values never come in result 
     if (x < 0) { 
      x += d; 
     } 
     return (int)(((long long)x * (long long)pow(x,n-1,d)) % (long long)d); 
    } 
}

我覺得你的代碼在邏輯上是正確的，但如果模d值足夠大，存在於int數據類型的數據溢出的問題。

例如。 (pow(x,n/2,d))*(pow((x),n/2,d))這裏兩個大的int值乘法會導致數據類型溢出。

來源

2017-06-05 08:20:53 Ultraviolet

計算pow（x，n）％d時的拐角案例

回答

相關問題