题目描述
给定 n 组 ai,bi,pi,对于每组数据,求出 ai^bi mod pi 的值。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含三个整数 ai,bi,pi。
输出格式
对于每组数据,输出一个结果,表示 ai^bi mod pi 的值。
每个结果占一行。
数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×109
样例
blablabla
算法1
快速幂
需要了解的知识:
数学:同余定理,(一个数的mod x的余数等于各个因数的余数之积再取mod)
计算机:二进制表示,位运算的与运算
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
// a^k mod p
int qmi(int a, int k, int p) {
int res = 1;
while (k) {//与运算判断,如果k末位为1
if (k & 1) res = (LL)res * a % p;
k >>= 1;//去掉k的二进制末位,即k的值*2
a = (LL)a * a % p;//k的二进制下一位,则迭代时即求a的平方mod p的值
}
return res;
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
int a, k, p;
scanf("%d%d%d", &a, &k, &p);
printf("%d\n", qmi(a, k, p));
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
Acwing 算法基础课
C++ 代码
blablabla
题目咧?