欧拉函数

定义

给定一个正整数N

证明

利用容斥原理

1. 从1~N中去掉所有p1, p2, … pk的倍数

n - n / p1 - n / p2 - … - n / pk;

1. 加上所有pi*pj的倍数
2. 减去所有pipjpk的倍数

…

将φ(n) = n * (1 - 1 / p1)(1 - 1 / p2)...(1 - 1 / pk)拆开，与容斥原理的结果一样，得证

例题

873. 欧拉函数

给定 n 个正整数 ai，请你求出每个数的欧拉函数。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个正整数 ai。
输出格式
输出共 n 行，每行输出一个正整数 ai 的欧拉函数。
数据范围
1≤n≤100,
1≤ai≤2×109
输入样例：

3
3
6
8

输出样例：

2
2
4

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int x = sc.nextInt();
            int cnt = x;
            for (int i = 2; i <= x / i; i++) {
                if (x % i == 0) {
                    cnt = cnt / i * (i - 1);
                    while (x % i == 0) {
                        x = x / i;
                    }
                }
            }
            if (x > 1) cnt = cnt / x * (x - 1);
            System.out.println(cnt);
        }
    }
}