欧拉函数

详细证明请移步大佬区

欧拉函数的简单结论：

$$\phi(N)= N \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times (1 - \frac{1}{p_3})··· \times (1 - \frac{1}{p_k})$$

$$（表示从1到N中一共有多少个数字与N互质，p表示N分解出来的质因数）$$

举个小栗子：

Tips:什么是互质？ 互质：当两个数的最大公约数仅为 1 时，称这两个数为互质。

栗子： 假设 $N = 6$, 首先将 $6$ 分解质因数，$6 = 2 ^ 1 \times 3 ^ 1$，接下来套用公式

$$\phi(6) = 6 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3}) = 6 \times \frac{1}{2} \times \frac{2}{3} = 2$$

$\therefore$ 在 1 到 6 中与 6 互质的数一共有2个。（分别是 1 和 5）

代码中，因为在公式中$(1 - \frac{1}{a})$很容易出现小数，这是不允许的，所以我们可以变化一下：

$$(1 - \frac{1}{a}) = (\frac{a}{a} - \frac{1}{a}) = \frac{a - 1}{a}$$

$$所以在代码中我们可以先除以 a 再乘上 a - 1$$

短小精悍的AC代码

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n -- )
    {
        int a;
        cin >> 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);
        cout << res << endl;
    }

    return 0;
}