一.欧拉函数 $\quad O(\sqrt a \ast n)$

对于一个大于1的自然数n来说,由算术基本定理可以将n分解为k个质数的乘积:$n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \ldots \times p_k^{\alpha_k}$
记欧拉函数为$\phi(n)$,
欧拉函数$\phi(n)$解决的问题:求解1~n中与n互质的数的个数
互斥:对于两个数a与b,若a和b的公约数只有1时,称a和b互斥
欧拉函数的具体公式:$\phi(n) = n \times \frac{p_1 -1}{p_1} \times \frac{p_2 -1}{p_2} \times \ldots \times \frac{p_k -1}{p_k}$

二.欧拉函数的证明:
证:
利用容斥原理来证明,如不懂,可以先看一下 小学数学:容斥原理
设sum为1~n中与n互斥
基本思路是去掉1~n中所有$p_1,p_2,\ldots,p_k的倍数$
①当$p_1,p_2,\ldots,p_k的倍数集合没有交集时$

$sum = n - \frac{n}{p_1} - \frac{n}{p_2} - \ldots - \frac{n}{p_k}$
②当$p_1,p_2,\ldots,p_k中的任意两个数的倍数集合拥有交集时$

这时在第①步时,会多减一次$p_i \times p_j$,所以需要加上一次$p_i \times p_j$
因此有$sum = n - \frac{n}{p_1} - \frac{n}{p_2} - \ldots - \frac{n}{p_k} + \frac{n}{p_1 \times p_2} + \frac{n}{p_1 \times p_3} + \ldots + \frac{n}{p_{k-1} \times p_k}$
依次类推有③,④,$\ldots$
最后将n提出来,就可出现$\phi(n) = n \times \frac{p_1 -1}{p_1} \times \frac{p_2 -1}{p_2} \times \ldots \times \frac{p_k -1}{p_k}$的形式
$\color{red}{证毕}$

三.时间复杂度分析:
算法的瓶颈主要在分解质因数上,分解质因数的时间复杂度为$\quad O(\sqrt a)$,但由于有n组数据,所以时间复杂度为$\quad O(\sqrt a \ast n)$

四.代码

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,res;
        cin>>a;
        res = a;
        for(int i=2;i<=a/i;i++)
        {
            if(a%i==0)
            {
                while(a%i==0)
                    a/=i;
                res = res / i*(i-1);
            }
        }
        if(a>1) res = res /a*(a-1);
        cout<<res<<endl;
    }
    return 0;
}

$\color{brown}{喜欢题解的话,欢迎点赞、收藏、关注(三连)喔,如有什么疑问,欢迎评论下方指出}$