模冪溢出

-3

public class Solution { 
    public int pow(int A,int B,int d) 
{ 
    if(A<0){ A=A+d;} 
    if (B==0) 
    { 
     if(A==0){return 0;} 
     return 1; 
    } 
    else if(B%2==0) 
    { 
     int y=pow(A,B/2,d); 
     return (y*y)%d; 
    } 
    else 
    { 
     return (A%d*pow(A,B-1,d))%d; 
    } 
}

}模冪溢出

我的代碼爲溢出，答：71045970 B：41535484 d：64735492

我的代碼給O/P：-17412928 預期的O/P： 20805472 哪裏出問題了？

有人可以修改我的代碼嗎？

來源

2015-06-05 S-N

'int'最多可容納32位信息〜-2kkk ... 2kkk，你平方''中（Y * Y）y'％D' ，'y'很容易超過1kk。 – user3707125

好的，我如何修改它？ –

這取決於您的輸入數據限制，如果它們不能超過'int'，那麼只需用'long'替換代碼中的所有'int's，否則您將不得不使用'BigInteger'。 – user3707125

BigInteger作爲一個modPow方法，這爲你平凡。

不給你預期的結果，但是給人一種不同的結果：

public int pow(int a, int b, int mod) { 
    if (a < 0) { 
     a = a + mod; 
    } 
    if (b == 0) { 
     if (a == 0) { 
      return 0; 
     } 
     return 1; 
    } else if (b % 2 == 0) { 
     int y = pow(a, b/2, mod); 
     return (y * y) % mod; 
    } else { 
     return (a % mod * pow(a, b - 1, mod)) % mod; 
    } 
} 

public int bigPow(int a, int b, int mod) { 
    return BigInteger.valueOf(a).modPow(BigInteger.valueOf(a), BigInteger.valueOf(mod)).intValue(); 
} 

private void test(int a, int b, int mod) { 
    System.out.println("Old - modPow(" + a + "," + b + "," + mod + ") = " + pow(a, b, mod)); 
    System.out.println("New - modPow(" + a + "," + b + "," + mod + ") = " + bigPow(a, b, mod)); 
} 

public void test() { 
    test(71045970, 41535484, 64735492); 
}

打印

Old - modPow(71045970,41535484,64735492) = -17412928 
New - modPow(71045970,41535484,64735492) = 44382800

如果你實際上是不是在找modPow（現在看起來有可能的）這裏有一個粗略的attemt使用BigInteger複製youyr算法。

public BigInteger bigPow(BigInteger a, BigInteger b, BigInteger mod) { 
    if (a.compareTo(BigInteger.ZERO) < 0) { 
     a = a.add(mod); 
    } 
    if (b.compareTo(BigInteger.ZERO) == 0) { 
     if (a.compareTo(BigInteger.ZERO) == 0) { 
      return BigInteger.ZERO; 
     } 
     return BigInteger.ONE; 
    } else if (!b.testBit(0)) { 
     BigInteger y = bigPow(a, b.shiftRight(1), mod); 
     return y.multiply(y).mod(mod); 
    } else { 
     return a.mod(mod).multiply(bigPow(a, b.subtract(BigInteger.ONE), mod)); 
    } 
}

現在給出預期的答案。

Old - modPow(71045970,41535484,64735492) = -17412928 
New - modPow(71045970,41535484,64735492) = 20805472

來源

2015-06-05 16:12:58 OldCurmudgeon

我不知道如何在我的代碼中使用biginteger。你能修改我的代碼嗎？ –

如果我嘗試用這個語句調用這個函數，p.bigPow（new BigInteger（71045970），new BigInteger（41535484），new BigInteger（64735492））; ，我得到BigInteger（長）構造函數不可見的錯誤，如何調用？ –

@ S-N - 使用（int）的Big integer.value; – OldCurmudgeon

請試試這個

public int Mod(int a, int b, int c) { 
    if(b==0){ 
     if(a==0) return 0; 
     else 
     return 1; 
    } 
    else if(b%2==0){ 
     long y=Mod(a,b/2,c); 

     return (int)(((long)(y*y))%(long)c); 
    }else{ 
     int k=a%c; 
     if(k<0){ 
      k+=c; 
     } 
     return (int)(((long)((long)k * (long)Mod(a,b-1,c)))%(long)c); 
    } 
}

來源

2015-11-04 07:09:01

回答

相關問題