在ACM竞赛中经常会遇到各种的求幂问题，这种问题一般情况下对应的数字都会很大，所以快速幂就会经常用到，快速幂很好用，就算没有弄清楚快速幂的原理，只要有模板很快就可以解题。
先说几个比较重要的公式： 模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p （1） // 这个公式等下写题目就会用到的 (a – b) % p = (a % p – b % p) % p （2） (a * b) % p = (a % p * b % p) % p （3） (a^b) % p = ((a % p)^b) % p （4） //快速幂的公式
结合律：
((a+b) % p + c) % p = (a + (b+c) % p) % p （5） ((a*b) % p * c)% p = (a * (b*c) % p) % p （6）
交换律：
(a + b) % p = (b+a) % p （7） (a * b) % p = (b * a) % p （8）
分配律：
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）
重要定理：
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10） 若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11） 若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a – c) ≡ (b – d) (%p)， (a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）
先上几个最常用的模板： 1.快速乘法 ： a*b
int qmul(int a,int b){// 根据数据范围可选择long long int ans=0; while(b){ if( b&1)ans+=a;//按位与完成位数为1的判断 b>>=1;a<<=1;//位运算代替/2和*2 } return ans; }2.快速乘法取模 (a*b)%mod
int qmul_mod(int a,int b,int mod){ int ans=0; while(b){ if((b%=mod)&1)ans+=a%=mod;//这里需要b%=mod 以及a%=mod b>>=1;a<<=1; } return ans%mod; //ans也需要对mod取模 }3.快速幂 a^b
int qpow(int a,int b){ if(a==0)return 0;//这是个坑，校赛被坑过，很多网上的实现都没写这一点 int ans=1; while(b){ if(b&1)ans*=a;//和快速乘法的区别 b>>=1;a*=a;//区别，同上 } return ans; }4.快速幂取模 (a^b)%mod
int qpow_mod(int a,int b,int mod){ if(a==0)return 0; int ans=1; while(b){ if(b&1)ans=(ans%mod)*(a%mod);//如果确定数据不会爆的话，可写成 ans*=a%=mod; b>>=1;a*=a%=mod;//等价于a=(a%mod)*(a%mod)，且将一个模运算通过赋值代替，提高了效率 } return ans%mod;//数据不会爆的话，这里的%运算会等价于第5中不断重复的 ans%mod }例题 POJ 1995 我是在VJ上直接拉过去的 就不放链接了 题目意思： 前面的废话省略，现在有一个游戏，每个人可以有两个数字Ai 和 Bi 现在要你把所以人的Ai^Bi求出来 然后全部加起来 再取模mod 结果输出就可以了 就是：(A1^B1+A2^B2+A3^B3+……………………An^Bn)%mod; 把上面那个式子的结果输出就可以了 数据范围不大 快速幂一遍过 但是这里用到了前面说的公式
(a + b) % p = (a % p + b % p) % p 这个对于多项也是成立的，然后利用上面的公式 将每个人的Ai 和 Bi快速幂取模 然后相加 全部加起来之后再取一次模 就拿到结果了 ok 上一下我的代码：
// POJ 1995 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; ll qpow_mod(ll a,ll b,ll mod){ if(a==0) return 0; ll ans = 1; while(b){ if(b&1) ans = (ans%mod)*(a%mod); b>>=1; a*=a%=mod; } return ans%mod; } int main(int argc, char const *argv[]) { int T; int m,n; ll sum; //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); scanf("%d",&T); while(T--){ sum = 0; scanf("%d",&m); scanf("%d",&n); for(int i=0;i<n;i++){ int a,b; scanf("%d %d",&a,&b); sum = sum + qpow_mod(a,b,m); } printf("%lld\n",sum%m); } return 0; }很尴尬 用了141ms 虽然不是特别快 但是也不慢了至少是Ac了 好了 快速幂就讲到这里 然后我觉得 毕竟是在搞竞赛的嘛，我认为准备模板啊这些的很正常， 而且在我现在实力不是特别的雄厚的时候，准备一些模板我觉得是可取的，虽然说不能完全的理解这个模板，但是多少懂一点，然后会用，在慢慢用的过程中自己在去领悟这个算法的真谛 之前打杭电的多校联赛，清华大学的team090这只队伍四次比赛三次AK，有一个很难的一题没有A出来，很佩服他们，和大神之间有很大差距，我们可以向他们学习，至少比昨天的自己更加优秀
遭遇了不理解，枯燥，TLE，WA………这些之后还在坚持的走下去，等看到了Ac，内心的成就感，我想这就是我们学算法的一个小意义所在吧 ！好了，要去吃饭了。一起加油！
