题目描述

求 a 的 b 次方对 p 取模的值。

样例

输入
3 2 7
输出
2
解释 
3^2 % 7 = 9 % 7 = 2 

算法

(快速幂) $O(logN)$

时间复杂度分析：对指数b进行二进制拆分logb位，只有二进制位为1的位是有用的位

C++ 代码

#include <iostream>

using namespace std;
typedef long long ll;

ll fastpower(ll a, ll b, ll p){
    ll ans = 1;
    while(b){
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans % p;
}

int main(){
    ll a, b, p;
    cin >> a >> b >> p;
    cout << fastpower(a, b, p) << endl;
    return 0;
}