P1226 【模板】快速幂||取余运算

skystars

【代码】解析见注释：

[C++] 纯文本查看 复制代码

#include <iostream>
using namespace std;
typedef long long ll; // ll更好打
ll qpow(ll a, ll b, ll p) { // O(logn) 的快速幂算法，递归形式简单易懂// 该函数可计算 a ^ b % p
        if (b == 0) return 1;
        if (b == 1) return a; // 递归边界条件
        if (b % 2 == 0) { // 如果b是偶数，那么就可以拆分成(a^(b/2))^2
                // 如 2^8 可以拆分成 2^4*2^4
                ll result = qpow(a, b / 2, p); // 一定要用变量存返回值，否则达不到O(logn)
                return result * result % p;
        }
        return qpow(a, b - 1, p) * a % p; // b是奇数，可以拆分成a^(b-1)*a
        //如 2^9 可以拆分成 2^8*2
}
int main()
{
        ll a, b, p;
        cin >> a >> b >> p;
        cout << a << "^" << b << " mod " << p << "=" << qpow(a, b, p);
        return 0;
}

Invefa

来观光一下qwq