P1226 【模板】快速幂——题解

解题思路

利用二进制快速幂。维护当前底数贡献 a 和答案 r；若指数最低位为 1，就把当前贡献乘入答案；每轮让底数平方、指数右移一位。所有乘法都及时取模。

正确性说明

循环中，已经处理的指数位贡献保存在 r，尚未处理的贡献由当前 a^b 表示。按最低位分解并平方右移保持乘积不变；指数归零时 r 即为原幂的模值。

复杂度分析

时间复杂度 $O(\log b)$，空间复杂度 $O(1)$。

易错点

即使 $b=0$，答案也应为 $1\bmod p$；输出格式中 mod 两侧各有一个空格。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
long long qpow(long long a,long long b,long long p){
    long long r=1%p;a%=p;
    while(b){if(b&1)r=r*a%p;a=a*a%p;b>>=1;}
    return r;
}
int main(){long long a,b,p;cin>>a>>b>>p;cout<<a<<'^'<<b<<" mod "<<p<<'='<<qpow(a,b,p)<<'\n';return 0;}

#include <bits/stdc++.h> using namespace std; long long qpow(long long a,long long b,long long p){ long long r=1%p;a%=p; while(b){if(b&1)r=ra%p;a=aa%p;b>>=1;} return r; } int main(){long long a,b,p;cin>>a>>b>>p;cout<<a<<'^'<<b<<" mod "<<p<<'='<<qpow(a,b,p)<<'\n';return 0;}