AcWing 89. a^b
原题链接
简单
作者:
泽生
,
2022-04-05 21:38:56
,
所有人可见
,
阅读 153
//快速幂 取模
//快速幂取模的时候 ,要在每一个运算的地方都取模
// 取模需要取3遍
//不是只要算a的b次方再%p吗, 为什么这有那么多次%p,res=resa%p; a=aa%p;?求大佬解答
//防止溢出
#include <iostream>
#include <stdio.h>
using namespace std;
//快速幂推
// 任何数 可以转换成 2进制
// x= 2_0 * 1 + 2_1 * 1 + 2_2 * 1 +2_3 * 0 +2_4 * 1+.....+2+31 * 1
// base ^x = base ^ ( 2_0 * 1 + 2_1 * 1 + 2_2 * 1 +2_3 * 0 +2_4 * 1+.....+2+31 * 1)
// = base ^ (1 * 1 + 1*2 + 1*4 ....)
// = 检查 x 对应位上是不是1即可
// = base * (1 * 1) * base * (1 *2) * base * (0 *4).....
// = base_1*1 * base_2*1 * base_4*0.....;
long long MyPow(long long a,long long b,long long p)
{
long long base = a;
long long x = b;
long long res = 1;
if (x < 0)
{
base = 1 /base ;
x = -x;
}
while (x) {
if (x & 1) {
res = base * res % p;
}
base = base * base % p;
x = x >>1;
}
return res;
}
int main()
{
long long a,b,p;
cin >> a >> b >> p;
long long x =MyPow(a,b,p);
cout <<x % p ;
return 0;
}