求欧拉函数

题目：给定 $n$ 个正整数 $a_{i}$ ，请你求出每个数的欧拉函数。

欧拉函数： $1∼N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记为 $ϕ(N)$ 。公式如下：
$ϕ(N) = N(1-1/p_{1})(1-1/p_{2})...(1-1/p_n)$
其中 $p_1, p_2, ..., p_n$ 是 $N$ 的质因子。
互质：两个数的最大公因数是1，即 $gcd(a, b) = 1$ 。

证明：

假设 $p,q,k$ 是 $N$ 的质因子，则在 $1∼N$ 中 $p$ 的倍数有 $p, 2p,3p,...,(N/p)p$ ，一共 $N/p$ 个。同理 $q$ 和 $k$ 的倍数有 $N/q,N/k$ 个。如果把这 $N/p,N/q,N/k$ 个数去掉，则 $N/pq,N/pk, N/qk$ 被多去了一次，需要加回来，但加回来后此时 $N/pqk$ 被少去了一次，所以需要再去掉一次，故有在 $1∼N$ 非 $p,q,k$ 的倍数有：
$\begin{aligned} S(N|p,q,k)&= N-(N/p+N/q+N/k) + (N/pq+N/pk+N/qk) - N/pqk\\ &= N(1-1/p)(1-/q)(1-1/k) \end{aligned}$
故若 $N = p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{n}^{k_{n}}$ ， $p_{1},p_{2},...,p_{n}$ 是 $N$ 的质因子，则 $1∼N$ 非 $p_{1},p_{2},...,p_{n}$ 的倍数有：
$\begin{aligned} S(N|p_{1}, p_{2},...,p_{n})= N(1-1/p_{1})(1-/p_{2})...(1-1/p_{n}) \end{aligned}$
而在 $1∼N$ 中与 $N$ 不互质的只有其质因子的倍数，所以与 $N$ 互质的数的个数即为 $1∼N$ 中非其质因子倍数的个数，从而有：
$ϕ(N) = N(1-1/p_{1})(1-1/p_{2})...(1-1/p_n)$

算法实现：

#include <iostream>
#include <cstring>
#include <algorithm>

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;
}

求欧拉函数

题目：给定 个正整数，请你求出每个数的欧拉函数。

证明：

算法实现：

推荐阅读更多精彩内容

题目：给定 $n$ 个正整数 $a_{i}$ ，请你求出每个数的欧拉函数。