Problem 374 Big Mod，大數字除法的餘數

這題是數學題，只要知道公式(a * b) mod c = ((a mod c) * (b mod c)) mod c，就可以將B^P mod M 不斷分割成小塊來避免溢位的問題，可以參考下面的方法：

unsigned long ComputeR(unsigned long B, unsigned long P, unsigned long M){
    if (P==1) return B % M;
    unsigned long i,res=1;
    i=1;
    res = B%M;
    while(2*i<P){
        res = (res*res)%M;
        i*=2;
    }
    return (res * ComputeR(B,P-i,M))%M;
}

Solved by Wellwind
p274題目連結
回ACM題庫目錄
回首頁