cms做视频网站,网页设计psd源文件,opensuse wordpress,porto wordpress目录
反复平方法#xff08;快速幂#xff09;#xff1a;
代码#xff1a;
例题#xff1a;快速幂求逆元 作用#xff1a; 快速求出 的结果。
时间复杂度#xff1a; O(logk) 如果使用一般做法#xff0c;从1循环到k#xff0c;时间复杂度是O(k) 反复平方法快速幂
代码
例题快速幂求逆元 作用 快速求出 的结果。
时间复杂度 O(logk) 如果使用一般做法从1循环到k时间复杂度是O(k) 反复平方法快速幂 将 用二进制表示 那么 因此 我们可以把 拆分成 因此我们只需要预处理出下面的就可以解决上述方法: 如何求解这些需要预处理 每次乘2 qmi(long a,long k,long p){long res 1;while(k!0){if((k1)1) res res*a%p; // 如果该位是1k k1; // 右移一位a a*a%p; //每次乘2}System.out.println(res);
} 该代码使用了一种位运算技巧。 位运算---求n的二进制表示中第k位是1还是0 (lowbit)-CSDN博客 例子 标准例题代码 给定 n 组 ai,bi,pi对于每组数据求出 的值。 输入格式 第一行包含整数 n。 接下来 n 行每行包含三个整数 ai,bi,pi。 输出格式 对于每组数据输出一个结果表示 的值。 每个结果占一行。 数据范围 1≤n≤100000, 1≤ai,bi,pi≤2×10^9 输入样例 2
3 2 5
4 3 9输出样例 4
1 import java.util.*;
import java.io.*;class Main{static final int N 100010;static int n;public static void main(String[] args) throws IOException{BufferedReader in new BufferedReader(new InputStreamReader(System.in));n Integer.parseInt(in.readLine());while(n--0){String[] s in.readLine().split( );long a Long.parseLong(s[0]);long b Long.parseLong(s[1]);long p Long.parseLong(s[2]);qmi(a,b,p); // 快速幂}}public static void qmi(long a,long b,long p){long res 1;while(b!0){if((b1)1) res res*a%p; // 如果该位是1b b1; // 右移一位a a*a%p; //每次乘2}System.out.println(res);}
} 例题快速幂求逆元 费马定理。 给定 n 组 ai,pi其中 pi 是质数求 ai 模 pi 的乘法逆元若逆元不存在则输出 impossible。 注意请返回在 0∼p−1 之间的逆元。 乘法逆元的定义 若整数 bm 互质并且对于任意的整数 a如果满足 b|a则存在一个整数 x使得 则称 x 为 b 的模 m 乘法逆元记为 。 b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时 即为 b 的乘法逆元。 输入格式 第一行包含整数 n。 接下来 n 行每行包含一个数组 ai,pi数据保证 pi 是质数。 输出格式 输出共 n 行每组数据输出一个结果每个结果占一行。 若 ai 模 pi 的乘法逆元存在则输出一个整数表示逆元否则输出 impossible。 数据范围 1≤n≤10^5, 1≤ai,pi≤2∗10^9 输入样例 3
4 3
8 5
6 3输出样例 1
2
impossible 解决方法 由题意可知 x 为 b 的模 m 乘法逆元记为 因此 由费马定理可知 因此 再使用快速幂解决
import java.util.*;
import java.io.*;
class Main{static int n;public static void main(String[] args) throws IOException{BufferedReader br new BufferedReader(new InputStreamReader(System.in));n Integer.parseInt(br.readLine());while(n--0){String[] s br.readLine().split( );int a Integer.parseInt(s[0]);int p Integer.parseInt(s[1]);long res qmi(a,p-2,p);if(a%p0) System.out.println(impossible);else System.out.println(res);}}public static long qmi(int a,int k,int p){long res 1;while(k!0){if((k1)1) res res*a%p;k k1;a (int)((long)a*a%p);}return res;}
}
