例题1:快速幂
给定 n 组 ai,bi,pi,对于每组数据,求出
的值。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含三个整数 ai,bi,pi。
输出格式
对于每组数据,输出一个结果,表示
的值。
每个结果占一行。
数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×109
输入样例:
2
3 2 5
4 3 9
输出样例:
4
1
答案:
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static int qmi(long a, long b, long p) {
long res = 1;
while (b > 0) {
if ((b & 1) > 0) res = Math.floorMod(res * a, p);
b = b >> 1;
a = (Math.floorMod(a * a, p));
}
return (int) res;
}
public static void main(String[] args) throws Exception {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] str = bufferedReader.readLine().split(" ");
int n = Integer.parseInt(str[0]);
for (int i = 0; i < n; i++) {
str = bufferedReader.readLine().split(" ");
long a = Long.parseLong(str[0]);
long b = Long.parseLong(str[1]);
long p = Long.parseLong(str[2]);
System.out.println(qmi(a, b, p));
}
}
}
快速幂的思路例子如图:
(过程很复杂,代码很简单)
例题2:快速幂求逆元
给定 n 组 ai,pi,其中 pi 是质数,求 ai 模 pi 的乘法逆元,若逆元不存在则输出 impossible
。
注意:请返回在 0∼p−1 之间的逆元。
乘法逆元的定义
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个数组 ai,pi,数据保证 pi 是质数。
输出格式
输出共 n 行,每组数据输出一个结果,每个结果占一行。
若 ai 模 pi 的乘法逆元存在,则输出一个整数,表示逆元,否则输出 impossible
。
数据范围
1≤n≤105,
1≤ai,pi≤2∗109
输入样例:
3
4 3
8 5
6 3
输出样例:
1
2
impossible
答案:
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static int qmi(long a, long b, long p) {
long res = 1;
while (b > 0) {
if ((b & 1) > 0) res = Math.floorMod(res * a, p);
b = b >> 1;
a = (Math.floorMod(a * a, p));
}
return (int) res;
}
public static void main(String[] args) throws Exception {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] str = bufferedReader.readLine().split(" ");
int n = Integer.parseInt(str[0]);
for (int i = 0; i < n; i++) {
str = bufferedReader.readLine().split(" ");
long a = Long.parseLong(str[0]);
long p = Long.parseLong(str[1]);
int t = qmi(a, p - 2, p);
if (a % p != 0)
System.out.println(t);
else
System.out.println("impossible");
}
}
}