思想

分解质因数 然后拼凑欧拉函数的方程

java代码

import java.util.*;
class Main{
    static int n = 0;
    static void getYinShu(int n){
        int k = n;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 2; i <= n / i; ++i){
            while(n % i == 0){
                map.put(i, map.getOrDefault(i, 0) + 1);
                n /= i;
            }
        }
        if(n > 1)map.put(n, map.getOrDefault(n, 0) + 1);

        long res = k;
        for(int a : map.keySet()){
            res = res * (a - 1) / a;
        }
        System.out.println(res);
    }
    public static void main(String[] args)throws Exception{
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        while(n -- != 0){
            int a = sc.nextInt();
            getYinShu(a);
        }
    }
}