欧拉函数初步

来看一下欧拉函数的定义：

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目.

欧拉函数记为

\phi (x)

例：

\phi (6)=2，
因为\underline{1}  2 3 4 \underline{5} 6

记数N分解质因数的结果是

N=p_{1} ^{\alpha1 }\times p_{2} ^{\alpha2}\times p_{3} ^{\alpha3}\times\cdot \cdot \cdot \times p_{k} ^{\alpha k}
 =\prod_{i=1}^{k} p_{i} ^{\alpha i}

则

\phi (x)=N(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\cdot \cdot \cdot (1-\frac{1}{p_{k}})=N\prod_{i=1}^{k}(1-p_{i})

例：

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

简要证明：（容斥原理） 要求1\~N中互质的数的个数，首先从1\~N中去掉Pi的倍数

N-[\frac{N}{p_{i}} ]

再加上所有Pi·Pj的倍数

再减去所有Pi·Pj·Pk的倍数

···以此类推

\phi(N)=N-[\frac{N}{P_i} ]+[\frac{N}{p_ip_j} ]-[\frac{N}{p_ip_jp_k} ]+\cdot \cdot \cdot \\  =   N(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})\cdot \cdot \cdot (1-\frac{1}{p_{k}})   =  N\prod_{i=1}^{k}(1-p_{i})

需要注意的是，在程序中因为int精度问题，一般将1-1/Pi写成*(Pi-1)/Pi

ll phi(int x){//返回x的phi(x)的值
    ll res=x;
    for(int i=2;i<=x/i;i++)
        if(x%i==0){
            res=res*(i-1)/i;//需要注意精度问题
            while(x%i==0)   x/=i;
        }
    if(x>1) res=res*(x-1)/x;//如果此时x>1，则x本身是一个较大的质数
    return res;
}

不难看出求解欧拉函数的时间复杂度和分解质因数一样，都是

O(\sqrt N)