快速幂对于k^n，每次将n分开
讨论n是否为偶数即可
时间复杂度自然从O(n)转变为了O(logn)
此处只呈现非递归版快速幂（不建议递归版快速幂）
#include<iostream> #include<cstdio> using namespace std; long long k,p,b; int main() { scanf("%lld%lld%lld",&b,&p,&k); long long re=1; while(p>0) { if(p&1) re*=b,re%=k; b*=b,b%=k; p>>=1; } cout<<re%k; return 0; }
原文：https://www.cnblogs.com/shzyk/p/9765679.html