打包的快速幂函数：
流行版：
数过大时，可将int型换long long型。
int mod_exp(int a, int b, int c) //快速幂取余a^b%c
{
int res, t;
res = 1 % c;
t = a % c;
while (b)
{
if (b & 1)//b的二进制和1的二进制进行位的按位与运算，其实等价于if(b%2==1)起到判断奇偶的功能，但计算机的位运算比较快。
{
res = res * t % c;
}
t = t * t % c;
b >>= 1;//即b=b>>1 b的二进制数右移一位赋值给b，右移时高位空缺补零。类比十进制数100右移相当于100/10=10;b>>1 等价于b/2;但计算机的位运算比较快。
}
return res;
}推理版：
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) %
b = b/2;
a = (a * a) % c;
}
return ans;
}总结：本算法的时间复杂度为O（logb），能在几乎所有的程序设计（竞赛）过程中通过，是目前最常用的算法之一。
知识背景：
离散数学中余数知识点：
1.(a+b)％m == (a％m+b％m)％m
2. a*b%c=((a%c)*b)%c
3. ab%c=(a%c)b%c（ab :a的b次方）
简介：
所谓的快速幂，实际上是快速幂取模的缩写，简单的说，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。
推理过程：
算法一：
直接设计算法——计算ab%c
//直接算出a^b的结果
int ans = 1;
for(int i = 1;i<=b;i++)
{
ans = ans * a;
}
ans = ans % c;算法二：
定理：a∗b%c=(a%c)∗b%c
引理：ab%c = (a%c)b%c
积的取余等于取余的积的取余。可以先让a关于c取余，这样可以大大减少a的大小。
int ans = 1;
a = a % c; //加上这一句,先对a取余
for(int i = 1;i<=b;i++)
{
ans = ans * a;
}
ans = ans % c;算法三：
既然某个因子取余之后相乘再取余保持余数不变，那么新算得的ans也可以进行取余。
int ans = 1;
a = a % c; //加上这一句,先对a取余
for(int i = 1;i<=b;i++)
{
ans = (ans * a) % c;//这里再取了一次余【改进】
}
ans = ans % c;算法一二三的总结：
算法在时间复杂度上没有改进，仍为O(b)，不过已经好很多的，但是在c过大的条件下，还是很有可能超时。
算法四：
int ans = 1;
a = a % c;
if(b%2==1)
ans = (ans * a) mod c; //如果是奇数，要多求一步，可以提前算到ans中
k = (a*a) % c; //我们取a^2而不是a
for(int i = 1;i<=b/2;i++)
{
ans = (ans * k) % c;
}
ans = ans % c;总结：时间复杂度变成了O(b/2)。
算法五：
当令k = (a * a) mod c时，状态已经发生了变化，所要求的最终结果即为(k)b/2 mod c而不是原来的ab mod c，这个过程是可以迭代下去的。
对于奇数的情形会多出一项a mod c，所以为了完成迭代，当b是奇数时，我们通过ans = (ans * a) % c;来弥补多出来的这一项，此时剩余的部分就可以进行迭代了。
形如上式的迭代下去后，当b=0时，所有的因子都已经相乘，算法结束。于是便可以在O（log b）的时间内完成了。
int ans = 1;
a = a % c;
while(b>0)
{
if(b % 2 == 1)
{
ans = (ans * a) % c;
}
b = b/2;
a = (a * a) % c;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103355.html
