本文主要是介绍【技巧】简单理解快速幂（求模），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【技巧】简单理解快速幂（求模）
今天讲了一个特别有用的东西就是快速幂，为了弄懂这个百度了一上午。。。还是没咋明白。。。
怕忘了就先开个博文记一下代码什么的。。。
快速幂，就是更快速地计算一个数的次方的方法。传统方法求幂计算，数小了还好，数大了就容易超时。
这个方法据说大部分比赛都不会超时，灰常地腻害呢~
具体理论总是太高大上了，还是举栗子好吃，简单又粗暴！
比如我们来算3的10次幂，把3乘10次脑袋就炸了，怎么算呢，这么算！
３＊３＊３＊３＊３＊３＊３＊３＊３＊３…………………………（１０个３相乘）①
＝（３＊３）＊（３＊３）＊（３＊３）＊（３＊３）＊（３＊３）…………………②
＝（３＊３）＾５
＝（（３＊３）＊（３＊３））＾２＊（３＊３）………………………………………③
…啥？并没有感觉多好算？废话！人脑算起来当然难算，我们叫电脑来算啊～
先来看①式，如果要电脑来算，１０个３相乘，就要乘９次；对于②式，五个３×３（把３×３看成一个整体）相乘，就要乘４次；对于③，就是两个（（３＊３）＊（３＊３））相乘再多乘一个多出来的（３＊３），只要乘３次就好了，对于电脑来讲，工作的循环次数越少就越省时间（这个时候我还没学时间复杂度呢，我就先这样理解了╮(╯_╰)╭）。
这样就总结出来一个公式！
ｎ＾ｐ （ｐ为偶数时） ｎ＾ｐ（ｐ为奇数时）
＝（ｎ＾２）＾（ｐ／２） ＝（（ｎ＾２）＾（ｐ／２））＊ｎ
＝（（ｎ＾２）＾２）＾（ｐ／２／２） ＝（（（ｎ＾２）＾２）＾（ｐ／２／２））＊ｎ
． ．
． ．
． ．
＝（ｎ＾ｐ）＊（１） ＝这个没固定公式（因为ｐ每次除２之后奇偶性不固定）
（这个公式前提是不管ｐ除多少个２商都是偶数）
而现实中情况更接近ｐ为奇数的那种情况，，对于那种情况，变换也很简单，当ｐ为奇数时，就把前面括号里的一堆东西（记为ｘ）平方掉再乘以（ｐ／２－０．５）（就是去尾法），注意还没完！还要再把去尾丢掉的一个ｘ再乘上，就变成了 原式＝（ｘ＾２）＊（ｐ／２－０．５）＊ｘ 当然程序里面如果ｐ是整型变量就不用减去０．５了。
综合上面的东西，可以得出快速计算ａ的ｐ次幂的函数代码：
long long QuickPow(long long a,long long p)
{long long ans=1;while(p){if(p%2==1)//当ｐ时奇数时，相当于往后面把那个少乘的ｘ补乘上去{ans=ans*a;}p/=2;a*=a;}return ans;
}有时候会叫你求ａ的ｐ次幂除以ｍｏｄ（ｍｏｄ只是一个数）的余数，这时候就要用到同余定理了，同余定理式子是这样的：
（ａ＊ｂ）除以ｃ的余数＝（ａ除以ｃ所得的余数）×（ｂ除以ｃ所得的余数），即（ａ＊ｂ）％ｃ＝（ａ％ｃ）＊（ｂ％ｃ），％是取余符号。
这样就会得到一个引理：
ＳＯ！
我们的代码就可以这样写了：
__int64 quickpow(__int64 a,__int64 p,__int64 mod)
{__int64 ans=1;a=a%mod;while(p){if(p%2==1){ans=ans*a%mod;}p/=2;a=a*a%mod;}return ans%mod;
}只是多往后面对ｍｏｄ取了个余罢了~
而我们上面的代码，就是当ｍｏｄ＝１时的情况。
任务完成！
华丽分割－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－＝－－＝－＝－＝－＝－＝－＝－＝－＝割分丽华
另附上学长给的代码：
//快速幂求模
#include<cstdio>
int quickpow(int n,int m,int mod)
{int ans=1,base=n;while(m){if(m&1){ans=(base*ans)%mod;}base=(base*base)%mod;m>>=1;printf("ans=%d base=%d m=%d\n",ans,base,m);}return ans;
}int main()
{int n,m,mod;while(~scanf("%d%d%d",&n,&m,&mod)){printf("%d\n",mod);printf("%d\n",quickpow(n,m,mod));}return 0;
}
唉，果然只有那些写出来让人看不懂的代码才能达到装逼的效果。。。→＿→
这篇关于【技巧】简单理解快速幂（求模）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
