记得在我第一天学习编程的时候老师就和我们说：为什么要学计算机呢？因为它速度快啊。一句玩笑话，不过确实快啊。这几天水题的时候就遇到了这样一个问题a^b%c，想了好几个方法都一直tle，一直不知道为啥，后来才知道有一个神奇的算法，快速幂，真是好用也神奇，真的是，我们全家都用它。
下面来介绍几个基本的求幂模的方法。
1.幂模的递归实现。直接贴上代码了，没什么好分析的。 long long cal(long long a,long long b,long long c) {//虽然看起来没有用循环来实现，不过很明显可以看出这是一个迭代的过程 if(b==1) return a%c; return cal(a,b-1,c)*a%c; } 2.幂模的循环实现。还是直接贴吧，估计以后也不看了。 long long cal(long long a,long long b,long long c) { a%=b; long long ans=a; for(int i=1;ireturn ans; } 3.下面要放大招了，就是我们今天要介绍的快速幂模。 long long cal(long long a,long long b,long long c) { long long ans=1; int num=a%c; while(b) { if(b&1) { ans=ans*num%c; } num=(num*num)%c; b>>=1; } return ans; } 下面来解释一下为什么可以这样做： 首先了解一点小知识：‘&’是个什么东东，第一次看的时候，笔者还是个弱逼（当然现在还是），现在算是懂了。这是位运算的一种。先将两个数字都转化为二进制，然后每位进行与运算，比如：7&8=0。为什么呢？
7的二进制表示是0111
8的二进制表示是1000
按位与的结果是0000也就是0，明白了这个再来讲讲和我们要做的有什么关系。首先，根据数学原理有：a^(b+c)=a^b*a^c。这样的话，我们
就可以把指数拆成几部分，每次将乘积的部分乘起来就可以得到答案。其中我们是把b拆成了二进制，为什么要这样呢？因为前一位是后一位的两倍，当所需数据是指数的时候就转化为底数的乘积。这一步的转化导致了我们计算量减少到了logn，然后每次取余就可以得到答案了。 同样
的原理，我们可以写出组合数的求模算法 long long C(long long n,long long m,long long p) { if(m>n)return 0;//不符合数学规律的情况 long long ans=1; for(int i=1;i<=m;i++) { long long a=(n+i-m)%p; long long b=i%p; ans=ans*(a*cal(b,p-2,p)%p)%p; } return ans; } 开始的时候写的东西一直过不了，一直不知道哪里该取余，后来发现一个好用但是无脑的方法就是：每次可能要用到取余的地方就一直取余，至少这样不会错。