0019：快速幂
题目链接：//www.luogu.com.cn/problem/P1226
给你三个整数 a,b,p，求 a^b mod p 的值。
这道题就是快速幂的模板题。
那么，什么是快速幂呢？
普通的幂运算就是让 b 个 a 相乘，但这样的时间复杂度较高，有 O（n）
接下来就要介绍一种时间复杂度只有O（log n）的算法。
众所周知，任何十进制数都可以拆成几个2^n 相加。如 11=1011=2^3+2^1+2^0。
同理，幂运算可以表示为a^1+a^2+a^3……（不是每个数都有，取决于指数）
进行幂运算时，我们可以将指数转化2进制，然后判断它在i维是否为1，如果是，让结果 *（a^i）。
上代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 long long a,b,p;//一定要用long long，不然只有36分 5 long long we=1;//一定要赋值为1，如果赋值为0的话所有结果全都是0 6 cin>>a>>b>>p; 7 cout<<a<<"^"<<b<<" mod "<<p<<"="; 8 while(b){ 9 if(b&1){//如果b的最后一位是1 10 we=(we*a)%p;//结果*a^i 11 } 12 a=(a*a)%p;//a平方 13 b>>=1;//舍弃b的最后一位 14 } 15 cout<<we; 16 }
