快速幂
暴力解法
基本思路:对于n组数据,分别循环b次求出a^b mod p
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
while(n -- )
{
int a, b, p;
long long res = 1;
cin >> a >> b >> p;
while(b -- ) res = res * a % p;
cout << res << endl;
}
return 0;
}
快速幂解法
快速幂迭代版 O(N * logb)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int a, b, p;
LL qmi(int a, int b, int p)
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % p;
b >>= 1;
a = (LL)a * a % p;
}
return res;
}
int main()
{
int n;
cin >> n;
while(n -- )
{
scanf("%d%d%d", &a, &b, &p);
cout << qmi(a, b, p) << endl;
}
return 0;
}