【題解】ZeroJudge d219: 00374 – Big Mod

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d219

  • 計算 B^P
    • P 為偶數,答案為 (B ^ (P/2))^2
    • P 為奇數,答案為 B * (B ^ (P//2))^2
#include <iostream>
using namespace std;

typedef long long ll;

ll bigMod(ll B, ll P, ll M) {
    if (P == 0) return 1;
    else if (P == 1) return B%M;
    else if (P%2 == 0) {
        ll tmp = bigMod(B, P/2, M) % M;
        return (tmp * tmp) % M;
    } else {
        ll tmp = bigMod(B, P/2, M) % M;
        return (B * tmp * tmp) % M;
    }
}

int main() {
    ll B, P, M;
    
    while (cin >> B >> P >> M) {
        cout << bigMod(B, P, M) << endl;
    }
    return 0;
}
分享本文 Share with friends