$$\color{Red}{欧拉函数}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

给定 n 个正整数 ai，请你求出每个数的欧拉函数。

欧拉函数的定义

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

输出共 n 行，每行输出一个正整数 ai 的欧拉函数。

数据范围

1 ≤ n ≤ 100

1 ≤ ai ≤ 2 × 10 ^ 9

输入样例：

3
3
6
8

输出样例：

2
2
4

证明

欧拉函数

两个数字互质的条件是：两个数如果最大公约数为1，则这两个数互质

需要用到容斥原理，证明部分日后我补齐。

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    static int n;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        while(n -- > 0){
            int x = Integer.parseInt(br.readLine());
            int ans = x;
            for (int i = 2; i <= x / i; i++) {
                if (x % i == 0){
                    ans = ans / i * (i - 1);
                    while (x % i == 0) x /= i;
                }
            }
            if(x > 1) ans = ans / x * (x - 1);
            System.out.println(ans);
        }
    }
}