输入样例:
2
3 2 5
4 3 9
输出样例:
4
1
解题思路:
Java代码:快速幂是用来快速求解a^k%p的结果,其中a,p,k的范围均可在10^9之内,其算法时间复杂度取决于指数k,为O(logk),比常规的O(n)快很多。
其具体做法是:将指数k按二进制形式分解,如a^7 = a ^ (2^2) ·a ^ (2^1)·a ^ (2^0),而a的幂又可以通过连续对a平方求,所以速度很快。
import java.io.*;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for(int i = 0; i < n; i++) {
String[] split = br.readLine().split(" ");
int a = Integer.parseInt(split[0]);
int k = Integer.parseInt(split[1]);
int p = Integer.parseInt(split[2]);
System.out.println(qmi(a, k, p));
}
}
public static int qmi(int a, int k, int p) {
int ans = 1;
while(k > 0) { // k没有被分解完
if((k & 1) == 1) ans = (int)((long)(ans * a) % p); // 分解二进制的最低位
a = (int)((long)a * a % p); // 将底数累乘
k >>= 1; // k的二进制形式右移一位
}
return ans;
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)