题目描述
给定 $n$ 组 $a_i,b_i,p_i$,对于每组数据,求出 $a^{bi}_{i} \ mod \ p_i$ 的值。
输入格式
第一行包含整数 $n$。
接下来 $n$ 行,每行包含三个整数 $a_i,b_i,p_i$。
输出格式
对于每组数据,输出一个结果,表示 $a^{bi}_{i} \ mod \ p_i$ 的值。
每个结果占一行。
数据范围
$1≤n≤100000$,
$1≤a_i,b_i,p_i≤2×10^9$
输入样例:
2
3 2 5
4 3 9
输出样例:
4
1
算法1
(暴力) $O(nk)$
数据达到了$2×10^9$,暴力肯定是不能过的,但是至少过了$6$个点hh
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
long long a,b,p;
scanf("%lld%lld%lld",&a,&b,&p);
long long res = 1;
for(int i = 1;i <= b;i ++){
res = res * a % p;
}
printf("%lld\n",res); // 答案
}
return 0;
}
算法2
(快速幂) $O(n log k)$
因为暴力不能过,我们就要像一个更优秀的算法,那我们就可以用快速幂来解决。
快速幂其实就是一种对暴力算法进行的优化,而不是一种全新的算法。
我们发现一次一次的平方太慢了,那我们就可以在平方的基础上再平方,那么,这样的时间复杂度就会得到优化。
那么原来的暴力做法时间复杂度为$O(nk)$,那么我们现在就可以把其中的$k$优化到$log$级别,成为$O(n log k)$
这种方法叫做反复平方法,也是快速幂的核心方法。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long qmi(int a,int k,int p){
int res = 1; // 快速幂答案
while(k){ // 直到k为0
if(k & 1) res = (long long) res * a % p; // 如果k的末尾为1的话,计算
k >>= 1; // 把k的末尾删掉,因为k的末尾已经计算完了
a = (long long) a * a % p; // 把a变成下一个数
}
return res;
}
int main(){
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
int a,k,p;
scanf("%d%d%d",&a,&k,&p);
printf("%lld\n",qmi(a,k,p));
}
return 0;
}
图中预处理的a^(2^0) = a^1 吧
个数也应该是logk+1个?
啊对,看着Y总上面写的没注意细节
改好了,感谢指出