AcWing 873. 欧拉函数

题目

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

欧拉函数的定义 $1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $\varphi(N)$。 若在算数基本定理中，$N={p_1}^{a_1}{p_2}^{a_2}...{p_m}^{a_m}$，则：$\varphi(n) = m(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_k)$ 输入格式 第一行包含整数 $n$。

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

输出格式 输出共 $n$ 行，每行输出一个正整数 $a_i$ 的欧拉函数。

数据范围 $1≤n≤100,1≤a_i≤2×10^9$ 输入样例：

3
3
6
8

输出样例：

2
2
4

思路

由欧拉函数有关性质，对于一个正整数，求其欧拉函数结果的公式为：$\varphi(n) = m(1 - 1/p_1)(1 - 1/p_2)...(1 - 1/p_k)$，其中 $p_i$ 为 $n$ 的质数。

代码

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    while (n -- )
    {
        int x;
        cin >> x;
        
        int res = x;
        for (int i = 2; i <= x / i; i ++ )
            if (x % i == 0)
            {
                res = res / i * (i - 1);
                while (x % i == 0) x /= i;
            }

        if (x > 1) res = res / x * (x - 1);
        
        cout << res << endl;
    }
    
    return 0;
}