信息学奥赛一本通1326：【例7.5】 取余运算（mod）

【题目描述】
输入b，p，k的值，求$b^p$ mod k的值。其中b，p，k×k为长整型数。
【输入】
输入b，p，k的值。
【输出】
求$b^p$ mod k的值。
【输入样例】
2 10 9
【输出样例】
2^10 mod 9=7

using ll = long long;
#include<iostream>
#include<cmath>
using namespace std;
int main() {
    ll b = 0, p = 0, k = 0, ans = 1;
    cin >> b >> p >> k;
    ll a = b, c = p, d = k;
    b %= k;
    while (p) {
        if (p & 1) {
            ans = (ans * b) % k;
        }
        b = (b * b) % k;
        p >>= 1;
    }
    cout << a << "^" << c << " mod " << d << "=" << ans;
    return 0;
}

p&1是利用二进制判断是否是奇数
p>>=1是通过位运算除2
快速幂就是利用(7X8)%3=(7%3)X(8%3),所以乘数取模再相乘就可以避免溢出的问题，但是仍可以提高效率
$3^{10}$=$9^5$=9*$81^2$,幂函数我们仍可以化简。这样就可以大大提高效率。