欧拉函数模板问题描述这是一道模板题。首先给出欧拉函数的定义即 Φ(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.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N110; static int a[]new int[N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); int nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 0; i n; i) { a[i]Integer.parseInt(st.nextToken()); } //首先给出欧拉函数的定义 // Φ(n) 表示的是小于等于n的数中和n互质的数的个数。 // 比如说Φ(6)2 因为是2和3 //当n是质数的时候显然有 Φ(n)n−1。 //暴力做法是枚举1-n的数 如果这个数和n的gcd为1 则加1 // for (int i 0; i n; i) { // method1(a[i]); // } //可以用欧拉函数公式优化 for (int i 0; i n; i) { method2(a[i]); } br.close(); bw.close(); } static void method2(int n) throws IOException{ int resn; for (int i 2; i * i n; i) { if(n%i0){ resres/i*(i-1);//先除以i 也一定能整除 while(n%i0){ n/i; } } } if(n1)resres/n*(n-1); bw.write(res\n); bw.flush(); } static void method1(int n) throws IOException{ int res0; for (int i 1; i n; i) { if(gcd(n,i)1){ res; } } bw.write(res\n); } static int gcd(int a,int b){ return b0?a:gcd(b,a%b); } }斐波那契数列题目描述斐波那契数列{F(1)F(2)1F(n)F(n−1)F(n−2)n2,n∈N∗{F(1)F(2)1F(n)F(n−1)F(n−2)​​n2,n∈N∗​给定一个正整数 NN求F(N)F(N)在模 10971097 下的值。输入描述第 11 行为一个整数 TT表示测试数据数量。接下来的 TT 行每行包含一个正整数 NN。1≤T≤1041≤T≤1041≤N≤10181≤N≤1018。输出描述输出共 TT 行每行包含一个整数表示答案。输入输出样例示例 1输入6 1 2 3 4 5 1000000000输出import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N110,mod(int)(1e9)7; static int a[]new int[N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); int tInteger.parseInt(st.nextToken()); for (int i 0; i t; i) { stnew StringTokenizer(br.readLine()); long nLong.parseLong(st.nextToken()); method(n); } br.close(); bw.flush(); bw.close(); } static void method(long n) throws IOException{ if(n1||n2){ bw.write(1\n); return; } long result[][]new long[1][2]; long begin[][]{{1,1}}; long base[][]{{1,1},{1,0}}; basemultiple(base,n-2); resultmatrixMul(begin, 1, 2, base, 2, 2); bw.write(result[0][0]\n); } static long[][] multiple(long base[][],long a){ //base^a long res[][]{{1,0},{0,1}};//单位矩阵 while(a0) { if((a1)1){ resmatrixMul(res,2,2,base,2,2); } aa1;//这个绝对不能取模 basematrixMul(base,2,2,base,2,2); } return res; } static long[][] matrixMul(long a[][],int row1,int col1,long b[][],int row2,int col2){ long res[][]new long[row1][col2]; for (int i 0; i row1; i) { for (int j 0; j col2; j) { for (int k 0; k col1; k) { res[i][j](res[i][j]a[i][k]*b[k][j]%mod)%mod; } } } return res; } }最大质因子个数【算法赛】问题描述给定一个正整数 NN请你在 22 到 NN 之间找到拥有不同质因子个数最多的整数并求出该整数的不同质因子的个数。输入格式第一行包含一个整数 TT1≤T≤1031≤T≤103表示测试用例的数量。接下来 TT 行每行包含一个正整数 NN2≤N≤10182≤N≤1018表示要求解的范围。输出格式对于每个测试用例输出一个整数表示在 22 到 NN 之间拥有最多不同质因子的整数的质因子个数。样例输入1 7样例输出2样例说明在 2∼72∼7 中22 的质因子有 [2][2]。33 的质因子有 [3][3]。44 的质因子有[2][2]。55 的质因子有[5][5]。66 的质因子有[2,3][2,3]。77 的质因子有[7][7]。因此66 是 2∼72∼7 中不同质因子个数最多的整数其拥有的不同质因子个数为 22。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N1010,mod(int)(1e9)7,cnt; static int a[]new int[N]; static int prime[]new int[N]; static boolean st[]new boolean[N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); int tInteger.parseInt(st.nextToken()); get_Prime(1000); for (int i 0; i t; i) { stnew StringTokenizer(br.readLine()); long nLong.parseLong(st.nextToken()); long p1; for (int j 0; j cnt; j) { if(pn/prime[j]){//相当于n/p0 这里怎么写只是为了防止溢出 // 若n / p1 p2 ... pk 0 这个数一定能在n以内找到 bw.write(j\n);break; } pp*prime[j]; } } br.close(); bw.flush(); bw.close(); } static void get_Prime(int n){ for (int i 2; i n; i) { if(!st[i]){ prime[cnt]i; } for (int j 0; jcnt i * prime[j] n; j) { st[i * prime[j]]true; if(i%prime[j]0)break; } } } }