pow（x、n）％dを計算中のコーナーケース

Question

xの正の値と負の値の両方について、上記の問題の作業コードを考え出しました。大部分の状況に対する答えは正しいですが、コーナーケースでコードが失敗し、問題の内容を見つけることができません。どのような条件私が行方不明です： `

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 

Answer 1

ここであなたの簡易版です。

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))ここでは、2つの大きなint値の乗算によってデータ型のオーバーフローが発生する可能性があります。