AcWing 89. a^b(关于快速幂的一个算法）

AcWing 89. a^b(关于快速幂的一个算法）

刚开始我以为用字符串解决，然后看到了快速幂，以前也是涉及过，但是没记住，然后又做一遍这样的题就觉得有点吃力。
老师讲课网址：

/

快速幂模板网址：

/

然后我还是不太明白他的原理是什么然后我把这个数变成了一个二进制我就明白了
5的二进制为101相当于2²+2⁰
这道题我们要用logn级别的算法，于是我们只能二分，然后会用到二进制转换的问题，比如说3⁵可以转换为3⁴⁺¹上面变成二进制类似于2^a+2^b+2^c+……+2^z这个时候就要用到二进制转换问题，把上面的指数变成二进制，遇到奇数说明这一位为1，就乘以t(t是这进制的对应的数）
画个图表示一下

就是把指数变成以2^a+2^b+2^c+……+2^z的形式 求一下解就可以了
代码如下

#include<iostream>
using namespace std;
int main(void)
{int a,b,p;cin>>a>>b>>p;int res=1%p;while(b){if(b&1) res=res*1LL*a%p;a=a*1LL*a%p;b>>=1;}cout<<res;
}