快速幂

题目描述
求 a 的 b 次方对 p 取模的值。

说到求解a的b次幂时，我们会想到幂运算的定义
然后就会自然而然地敲下一串的循环来计算这个值。但是这样实在是太慢了，如果指数比较大的话，就要好长好长的时间…
我们可以利用二进制的特点来减少计算量。指数b的二进制表示为101010111…根据二进制数转换十进制数的方法，他就一定能表示为

(t1,t2,t3就是二进制表示中为1的数位）循环看每一位是不是1，是1就乘上底数a。a做出相应变化，即每循环一位就乘2。
这样int范围内最多也只会计算32次

#include<iostream>using namespace std;typedef long long LL;LL qpow(LL a,LL b,LL c)
{if(b==0) return 1;long long res=1;while(b){if(b&1) res=res*a%c;a=a*a%c;b>>=1;}return res;
}int main()
{LL a,b,c;cin>>a>>b>>c;cout<<qpow(a,b,c)%c;
}