题目描述

pow(a, b) % mod = (a % mod) * (a % mod) * (a % mod) * ....
= (a * a) % mod * (a * a) % mod * (a * a) % mod * …
分解完求最后还要 再求模。

样例

#include <iostream> 
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;


int main() {
    long long  a, b, mod;
    cin >> a >> b >> mod;
    if (mod == 1 ) {
        cout << 0 << endl;
        return 0;
    }
    if (b == 0) {
        cout << 1 << endl;
        return 0;

    }
    if (b < 0) {
        cout << 0 << endl;
        return 0;
    }
    long long r = 1;
    a = a % mod;
    while(b > 1) {//(a * a) % mod * (a * a) % mod * (a * a) % mod * .....* a % mod;
        if ( b % 2) r = (r * a) % mod;//如果b是奇数，取出一位。
        a = (a * a) % mod;
        b /= 2;
    }
    cout << (r * a) % mod << endl;
    return 0;
}