莫欺少年穷，修仙之旅在这开始—>算法基础课题解

欧拉函数

定义： 欧拉函数（Euler’s totient function），即 $\varphi(n)$ ，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

结论： 若 $n=\prod\limits_{i=1}^kp_i^{a_i}$，则 $\varphi(n)=n\prod\limits_{i=1}^k(1-\dfrac{1}{p_i})$

定理： 若 $n=p^a$，其中 $p$ 是质数，那么 $\varphi(n)=p^a-p^{a-1}$。（由定义可知）

证明： $$ \begin{aligned} \varphi(n)&=\prod\limits_{i=1}^k\varphi(p_i^{a_i})\\\\&=\prod\limits_{i=1}^kp_i^{a_i}-p_i^{a_i-1}\\\\&=\prod\limits_{i=1}^kp_i^{a_i}(1-\dfrac{1}{p_i})\\\\&=n\prod\limits_{i=1}^k(1-\dfrac{1}{p_i}) \end{aligned}$$

#include<bits/stdc++.h>

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