​快速幂、费马小定理、约数的个数、欧拉函数模板、矩阵快速幂

快速幂快速幂题目描述输入 bpkbpk 的值求 bpmodkbpmodk 的值。其中 2≤b,p,k≤1092≤b,p,k≤109 。输入描述三个整数 b,p,kb,p,k。输出描述输出 bpmodksbpmodksss 为运算结果。输入输出样例示例输入2 10 9输出7运行限制最大运行时间1s最大运行内存: 128Mimport java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); String[] g br.readLine().split(\\s); // 修复支持多个空格 int a Integer.parseInt(g[0]); int p Integer.parseInt(g[1]); int k Integer.parseInt(g[2]); quickMi(a, p, k); } static void quickMi(long a, long p, long mod) { long res 1; while (p 0) { if ((p 1) 1) { res res * a % mod; } a a * a % mod; p p 1; } System.out.println(res % mod); } }费马小定理乘法逆元乘法逆元题目描述给定一个正整数 NN求它在模 10971097 下的乘法逆元。输入描述第 11 行为一个整数 TT表示测试数据数量。接下来的 TT 行每行包含一个正整数 NN。1≤T≤1051≤T≤1051≤N≤1091≤N≤109。输出描述输出共 TT 行每行包含一个整数表示答案。输入输出样例示例 1输入5 1 2 3 4 5输出1 500000004 333333336 250000002 400000003运行限制最大运行时间1s最大运行内存: 128Mimport java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; public class Main { static int N 1000010,mod(int)1e97; // static int prime[]new int[N]; // static int mi[]new int[N]; // static int ind; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int tInteger.parseInt(br.readLine()); // String g[] br.readLine().split( ); // int aInteger.parseInt(g[0]),pInteger.parseInt(g[1]),kInteger.parseInt(g[2]); BigInteger mBigInteger.valueOf(mod); for (int i 0; i t; i) { int nInteger.parseInt(br.readLine()); BigInteger aBigIntegerBigInteger.valueOf(n); System.out.println(aBigInteger.modInverse(m).toString()); } // quickMi(a,p,k); } }import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N 1000010,mod(int)1e97; // static int prime[]new int[N]; // static int mi[]new int[N]; // static int ind; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int tInteger.parseInt(br.readLine()); // String g[] br.readLine().split( ); // int aInteger.parseInt(g[0]),pInteger.parseInt(g[1]),kInteger.parseInt(g[2]); for (int i 0; i t; i) { int nInteger.parseInt(br.readLine()); // a x 1 (mod) // a x a^(p-1) // xa^(p-2) quickMi(n,mod-2,mod); } } static void quickMi(long a,long p,long mod){ long res1; while(p0){ if((p1)1){ resres*a%mod; } aa*a%mod; pp1; } System.out.println(res%mod); } }约数的个数问题描述0约数的个数 - 蓝桥云课给定长度为 nn 的序列 aa输出 ∏i1naii1∏n​ai​ 的约数个数。结果对 10971097 取模。输入格式第一行输入包含一个正整数 nn。(1≤n≤100)(1≤n≤100)第二行输入包 nn 个数字 aiai​。(1≤ai≤2×109)(1≤ai​≤2×109)输出格式输出 ∏i1naii1∏n​ai​ 的约数个数。结果对 10971097 取模。样例输入4 2 4 5 6样例输出20import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; public class Main { static int N 1000010,mod(int)1e97; // static int prime[]new int[N]; // static int mi[]new int[N]; // static int ind; static MapInteger, Integer mapnew HashMapInteger, Integer(); public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); String g[] br.readLine().split( ); // int aInteger.parseInt(g[0]),pInteger.parseInt(g[1]),kInteger.parseInt(g[2]); for (int i 0; i n; i) { int numInteger.parseInt(g[i]); total(num); } long res1; for(int key:map.keySet()){ resres*(map.get(key)1)%mod; } System.out.println(res); } static void total(int num){ int nnum; for (int i 2; i*i num; i) { if(n%i0){ while(n%i0){ map.put(i, map.getOrDefault(i, 0)1); n/i; } } } if(n1)map.put(n,map.getOrDefault(n,0)1); } }欧拉函数模板问题描述这是一道模板题。首先给出欧拉函数的定义即 Φ(n)Φ(n) 表示的是小于等于 nn 的数中和 nn 互质的数的个数。比如说 Φ(6)2Φ(6)2当 nn 是质数的时候显然有 Φ(n)n−1Φ(n)n−1。题目大意给定 nn 个正整数请你求出每个数的欧拉函数。输入格式输入共两行。第一行输入一个整数表示 nn 。第二行输入 nn 个整数。输出格式输出共 nn 行每行输出 11 个整数表示对应数字的欧拉函数。样例输入3 3 6 8样例输入2 2 4说明小于等于 33 的数中与 33 互质的有1,21,2。小于等于 66 的数中与 66 互质的有1,51,5。小于等于 88 的数中与 88 互质的有1,3,5,71,3,5,7。评测数据规模保证对于所有数据有1≤n≤1001≤n≤100输入的 nn 个整数范围为 [1,2×109][1,2×109] 。import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; public class Main { static int N 1000010,mod(int)1e97; // static int prime[]new int[N]; // static int mi[]new int[N]; // static int ind; static MapInteger, Integer mapnew HashMapInteger, Integer(); public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int nInteger.parseInt(br.readLine()); String g[] br.readLine().split( ); // int aInteger.parseInt(g[0]),pInteger.parseInt(g[1]),kInteger.parseInt(g[2]); for (int i 0; i n; i) { int numInteger.parseInt(g[i]); clac(num); } } static void clac(long num){ long resnum; for (int i 2; i*i num; i) { if(num%i0){ resres/i*(i-1); while(num%i0){ num/i; } } } if(num1)resres/num*(num-1); System.out.println(res); } }矩阵快速幂问题描述一个 m×nm×n 的矩阵是一个由 mm 行 nn 列元素排列成的矩形阵列。即形如A[a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮am1am2⋯amn].A⎣⎢⎢⎢⎢⎡​a11​a21​⋮am1​​a12​a22​⋮am2​​⋯⋯⋱⋯​a1n​a2n​⋮amn​​⎦⎥⎥⎥⎥⎤​.给定一个 n⋅nn⋅n 的矩阵 AA求解 AkAk每个元素需对 10971097 取模。输入格式第一行输入 22 个正整数 n,kn,k。接下来 nn 行每行 nn 个正整数表示矩阵的具体元素。输出格式输出 nn 行每行 nn 个正整数第 ii 行第 jj 个数表示 (Ak)i,j(Ak)i,j​每个元素对 10971097 取模。样例输入3 3 1 2 3 4 5 6 7 8 9样例输出468 576 684 1062 1305 1548 1656 2034 2412评测数据规模1≤n≤100,0≤k≤1012,∣Aij∣≤10001≤n≤100,0≤k≤1012,∣Aij​∣≤10暴力超时import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Main { static int N 110,mod(int)1e97; static int a[][]new int[N][N]; static int back[][]new int[N][N]; static MapInteger, Integer mapnew HashMapInteger, Integer(); public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); // int nInteger.parseInt(br.readLine()); String g[] br.readLine().split(\\s); int nInteger.parseInt(g[0]),kInteger.parseInt(g[1]); for (int i 0; i n; i) { g br.readLine().split( ); for (int j 0; j n; j) { a[i][j]Integer.parseInt(g[j]); back[i][j]a[i][j]; } } for (int i 1; i k; i) { int aa[][]new int[n][n]; for (int j 0; j n; j) { aa[j]Arrays.copyOfRange(a[j],0, n); } int c[][]new int[n][n];//每个新的结果必须从0开始 for (int j 0; j n; j) { for (int m 0; m n; m) { for (int l 0; l n; l) { c[j][m](int)(c[j][m](long)aa[j][l]*back[l][m])%mod; //a[j][l]可能被这次更新过了 所以a要先备份 } } } for (int j 0; j n; j) { a[j]Arrays.copyOfRange(c[j],0, n); } } for (int i 0; i n; i) { for (int j 0; j n; j) { System.out.print(a[i][j] ); } System.out.println(); } } }矩阵快速幂import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N 110,mod(int)1e97; static int a[][]new int[N][N]; //static int back[][]new int[N][N]; static int ans[][]new int[N][N]; public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); // int nInteger.parseInt(br.readLine()); String g[] br.readLine().split( ); int nInteger.parseInt(g[0]); long kLong.parseLong(g[1]); for (int i 0; i n; i) { g br.readLine().split( ); for (int j 0; j n; j) { a[i][j]Integer.parseInt(g[j]); } } for (int i 0; i n; i) {//定义为单位矩阵 ans[i][i]1; } while(k0){ if((k1)1){ ansmultiple(ans, a); } kk1; amultiple(a, a); } for (int i 0; i n; i) { for (int j 0; j n; j) { System.out.print(ans[i][j] ); } System.out.println(); } } static int[][] multiple(int a[][],int b[][]){ int res[][]new int[a.length][b[0].length]; for (int i 0; i a.length; i) { for (int j 0; j b[0].length; j) { for (int j2 0; j2 a[0].length; j2) { res[i][j](int)((res[i][j](long)a[i][j2]*b[j2][j])%mod); } } } return res; } }