首页 > 代码库 > 快速幂取模和快乘取模
快速幂取模和快乘取模
一、快速幂取模概念
快速幂取模，顾名思义，就是快速的求一个幂式的模(余)，比如a^b%c，快速的计算出这个式子的值。
在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。
二、快速幂取模算法实现
1）很容易能想到，循环b次，每次乘a，最后对c取余就可以了。
int ans = 1; for(int i = 1; i<=b; i++) { ans = ans * a; } ans = ans % c;
这个朴素算法的问题是：
1.如果a和b都很大，那么ans很有可能超出long long类型，最后结果错误
2.如果b很大，这样计算会超时。
所以对这个算法需要改进
2）有一个很简单的公式如下：
证明略，由上面公式我们可以对上面算法进行优化
int ans = 1; a = a % c; for(int i = 1; i<=b; i++) { ans = (ans * a) % c；//这里再取了一次余 } ans = ans % c；
这样就解决了超出long long的问题了，但是时间复杂度还没有降低。
3）为了解决超时问题，我们可以使用下面的公式，证明略
int ans = 1; a = a % c; if(b%2==1) ans = (ans * a) mod c; //如果是奇数，要多求一步，可以提前算到ans中 k = (a*a) % c; //我们取a2而不是a for(int i = 1; i<=b/2; i++) { ans = (ans * k) % c; } ans = ans % c;
这样，我们就把时间复杂度降到b/2了，观察上式子，可以发现，当我们令k = (a * a) mod c时，状态已经发生了变化，我们所要求的最终结果即为(k)^b/2 mod c而不是原来的a^b mod c，当下次求(k)^b/2 mod c时，我们可以继续对这个式子记成上面格式，我们发现这个过程是可以重复下去的。
4）最终我们得到快速幂取模的算法
int ans = 1; a = a % c; while(b>0) { if(b % 2 == 1) ans = (ans * a) % c; b = b/2; a = (a * a) % c; }
三、快速幂取模模板
int PowerMod(int a, int b, int c)//a^b%c { int ans = 1; a = a % c; while(b>0) { if(b % 2 = = 1) ans = (ans * a) % c; b = b/2; a = (a * a) % c; } return ans; }
四、快乘取模
1.概念：
快速乘法是求两个数相乘，即求解a*b%c，很明显这个不会超时，但是如果当a和b特别大的时候，两个数相乘可能超过long long 范围，所以要使用快速乘法，因为在加法运算的时候不会超，而且可以直接取模，这样就会保证数据超不了了。快速乘法的思想和快速幂的思想一样，快速幂是求一个数的高次幂，快速乘法是求两个数相乘。
2.算法实现：
这样的式子和a^b%c很像，所以可以用类似于快速幂取模的方法来做。即，将b写成二进制来看，然后拆开相加（正因为二进制的特殊性，才有快速乘和快速幂的成功），比如下面的例子：
32+16+4=52 （实际操作过程中，每次相加都取模）
这一过程和快速幂取模非常相似。
3.模板：
int multiMod(int a, int b, int c) { int ans = 0;//注意初始化是0，不是1 while (b) { if (b & 1) ans=(ans+a)%c; a = (a + a) % c;//和快速幂一样，只不过这里是加 b >>= 1; } return ans; }
快速幂取模和快乘取模