本文主要是介绍Acwing---873. 欧拉函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
欧拉函数
- 1.题目
- 2.基本思想
- 3.代码实现
1.题目
给定 n 个正整数 ai，请你求出每个数的欧拉函数。
欧拉函数的定义
输入格式
第一行包含整数 n n n。
接下来 n n n 行，每行包含一个正整数 a i ai ai。
输出格式
输出共 n n n 行，每行输出一个正整数 a i ai ai 的欧拉函数。
数据范围
1 ≤ n ≤ 100 , 1≤n≤100, 1≤n≤100,
1 ≤ a i ≤ 2 × 1 0 9 1≤ai≤2×10^9 1≤ai≤2×109
输入样例：
3
3
6
8
输出样例：
2
2
4
2.基本思想
3.代码实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;public class _873欧拉函数 {private static int phi(int a) {int res = a;for (int i = 2; i <= a / i; i++)if (a % i == 0) {res = res / i * (i - 1);while (a % i == 0) a /= i;}if (a > 1) res = res / a * (a - 1);return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();while (n-- > 0) {int x = sc.nextInt();System.out.println(phi(x));}}
}
这篇关于Acwing---873. 欧拉函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
