为什么使用快速幂
在求a^b%p的值中，明显要乘b次a，所以时间复杂度是O(b)。为了降低时间复杂度，引入快速幂的算法。
举例说明：
比如要求3^10
①：
可以采用这种思路：幂为偶数时候 底数平方 指数除以2
用到公式 a^b=(a^2)^(b/2)
②：
则变成了9^5 当幂为奇数时候 我们只要提出一个底数 则幂又成了偶数 所以可以把ans初始化为1
则ans*=提出的底数9
用到公式：a^b=a*a^(b-1)
③：
如此操作下去 最后幂 一定会变成0 此时答案就算出来了
④：
由于要取模，所以就在每一次计算 提出底数与ans相乘的时候取模即可
用到公式:(a*b)%p=((a%p)*(b%p))%p
意思就是中间计算结果取模 对最后结果没有影响
快速幂代码段：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<set>
#include<sstream>
using namespace std;
long long fast_power(long long a,long long b,long long p){long long ans=1;while(b){if(b%2==1){ans*=a;ans%=p;}b/=2;a*=a;a%=p;}return ans;
}int main(){long long a,b;int p;cin>>a>>b>>p;a%=p;cout<<fast_power(a,b,p);return 0;
}
fast_power函数详解：
while循环 判断指数b 只要指数b不等0：
1.若指数b为奇数 则ans*=底数a 也就是提出去一个底数 然后注意取模p
2.由于奇数-1一定会变成偶数 所以指数为偶数时 就执行除以2的操作 b/=2 底数平方 a*=a;
3.如此循环 直到指数b=0，此时的ans即为答案。
时间复杂度分析：
指数b一直除以2 最后变成0 则进行log2(b)次循环 所以时间复杂度为O(logb) 大大降低
