算法总结—快速幂 最后更新于 2025-03-31 12:36:15

# 快速幂 要求 $a^b\bmod p$ 是多少，可以花 $\mathcal{O}(b)$ 的时间计算，但是如果 $b=10^{18}$ 就不好算了。这时可以对 $b$ 进行二进制拆分，例如 $b=15$ 时，二进制拆分就是 $(1111)_2$，那么 $a^{15}=a^8\times a^4\times a^2\times a^1$，这样可以在计算过程中将 $a$ 不停的 乘以 $a$，如果当前二进制位是 $1$，就把答案乘上 $a$，这样就可以在 $\mathcal{O}(\log b)$ 的时间内解决了。 ## [【模板】快速幂](https://www.luogu.com.cn/problem/P1226) ### 代码 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int qpow(int a,int b,int mod){ int ans=1; while(b){ if(b&1){ ans=(ans*a)%mod; } a=(a*a)%mod; b/=2; } return ans; } signed main(){ int a,b,mod; cin>>a>>b>>mod; int cnt=qpow(a,b,mod); printf("%d^%d mod %d=%d",a,b,mod,cnt); return 0; } ```