快速幂详解以及例题解析
借鉴两位大神的笔记，略有通悟
在这里我总结一下：
快速幂算法用来求解大数的取幂操作，这应用的数学知识有两点
1.
2.算法基础在于模运算的基本性质： (a*b)%n = ( (a%n) * (b%n) ) %n
下面我通过代码模板进行详细的解释：
#include"iostream"
#include"cstdio"
using namespace std;
//首先，每次迭代都有这个公式，所以，只要新的b还是2的倍数用1式，否则用二式
//在奇数的情况下，基本性质中应用
int main()
{
int a,b,c; //a为底数,b为指数,c为模
cin>>a>>b>>c;
int ans=1;
while(b>0)
{
if(b%2==1) ans=(ans%c*a%c)%c; //这里运用了第二点基本性质(a*b)%n = ( (a%n) * (b%n) ) %n
b=b/2;
a=(a%c*a%c)%c; //这里运用了迭代的过程，上面的公式中的k（就是这里的a）不断地扩大倍数
//这里的a*a的意思是，只要b现在是偶数我就可以继续迭代
//k^b%c=(k^(b/2)*k^(b/2))%c=((k^2)^(b/2))%c=(k%c*k%c)^(b/2))%c=a^(b/2)%c (a=k%c*k%c)
}
//咋循环控制语句中，b=1的步骤是一定会执行的，所以，ans的值时钟控制在c一下，这一点保证了21行的等式，保证了算法的实现
cout<<ans<<endl;
return 0;
}
