这篇博客归纳总结了快速幂的一些应用，快速幂只是一个工具，难点不在于实现而在于在合适的时候把它用上。选取了几个可以使用快速幂解决的问题，由显而易见到较为复杂难以辨别。
快速幂算法：
基础：(a+b)%c=(a%c+b%c)%c a*b%c=(a%c*b%c)%c;
故：a^b=a^(2^x1+2^x2+..........+2^xn) 若b为奇数，则xn为0，若b为偶数，则xn为1
将b转化为2的次方和后可将复杂度由O(b)降为O(log2b)
快速幂代码模板：
int quick_pow(int a,int b) { int base=a,ans=1; while(b)//一直计算到b为0 { if(b&1) ans*=base;//b为奇数时乘上base base*=base;//base平方 b=b>>1;//指数减半 } return ans; }第一题：杭电1061 快速幂模基础板题http://acm.hdu.edu.cn/showproblem.php?pid=1061
分析：求N^N的最后一位数字。直接算太大，于是只算最后一位数字N的N次方，在每一步取模即可
#include <bits/stdc++.h> using namespace std; int quick_pow(int a,int b) { int base=a,ans=1; while(b) { if(b&1) ans=(ans*base); base=(base*base); b=b>>1; } return ans; } int main() { int n,t; cin>>t; while(t--) { cin>>n; cout<<quick_pow(n,n)<<endl; } return 0; }
第二题：神秘钥匙————选自牛客网小白月赛8
比赛链接：https://www.nowcoder.com/acm/contest/214#question
题目链接：https://www.nowcoder.com/acm/contest/214/C
分析：显然结果等于 这道题并不容易察觉出是快速幂。由于n的范围为10^9，如果依次计算求和肯定超时。根据组合数公式可得到该式可以转化为n*2^(n-1)，于是可利用快速幂取模
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1000000007; ll quick_pow(ll a,ll b) { ll ans=1,base=a; while(b) { if(b&1) ans=(ans*base)%MOD; base=(base*base)%MOD; b=b>>1; } return ans; } int main() { ll n; cin>>n; cout<<quick_pow(2,n-1)*n%MOD<<endl; return 0; }第三题：后续继续更
