快速幂取模

此内容分2步

1、 快速幂

快速幂就是运用中间运算数值加减快速运算的一种运算模式
比如：pow（a，b）；

快速幂使用第一步

将pow（a，b）中的b转化为2进制数
比如100转化2进制为1100100；

快速幂使用第二步

应用1100100对应在2进制的数， 添加在幂的底数上，a⁶⁴+a³²*a⁴
在其中a⁴,a³²可以在累乘的过程中得到，a⁶⁴无需计算既，减少了计算量。

代码演示

//pow(a,b);
int  a,b;
int total=1,base=a;
while(b!=0)
{if（b%2==1）{total=total*base;}base=base*base;b=b/2;
}
//total =......

取模

再次了解一个概念，在相乘的数值中任意阶段取模最后结果不变。
举个栗子：（1020）mod 7==（10 mod 7 * 20 mod 7）mod 7；
写成公式变为(ab)mod c=(a mod c * b mod c)c;
那么我们把取模添加到快速幂的累乘阶段就行了。

代码演示

//pow(a,b) mod c
int total=1,base=a;
while(b!=0)
{if（b%2==1）{total=total*base%c;}base=base*base%c;b=b/2;
}
//total=.........