欧拉函数的定义

欧拉函数，即 $\varphi(n)$，表示 $1\sim n$ 与 $n$ 互质的数的个数。

特别的，$\varphi(1)=1$。

当 $n$ 为质数时，显然有 $\varphi(n)=n-1$。

积性函数

积性函数的定义：对于任意满足 $\gcd(a,b)=1$ 的 $a$ 和 $b$，如果满足 $f(ab)=f(a)\times f(b)$，则称 $f$ 函数为积性函数。

欧拉函数是积性函数。证明如下：

对于两个互质的数的乘积 $n$，必然可以表示为 $n=q^ap^b$（$p$、$q$ 为质数）。

我们用 $g(x,y)$ 表示 $\le x$ 的数中 $y$ 的的倍数的个数，则有 $g(n,p)=p^{a-1}q^b$，$g(n,q)=p^aq^{b-1}$，$g(n,pq)=p^{a-1}q^{b-1}$。

由容斥原理得 $n=g(n,p)+g(n,q)-g(n,qp)+\varphi(n)$。

$$ \begin{aligned} {}\varphi(n)=&n-g(n,p)-g(n,q)+g(n,qp)\\ =&p^aq^b-p^{a-1}q^b-p^aq^{b-1}-p^{a-1}q^{b-1}&\\ =&(p^a-p^{a-1})\times(q^b-q^{b-1})&\\ =&\varphi(p^a)\times\varphi(p^b) \end{aligned} $$

得证欧拉函数为积性函数。

欧拉函数的求值

对于 $n={p_1}^{k_1}{p_2}^{k_2}\cdots {p_r}^{k_r}$，由积性函数的性质我们可以得到：

$$ \begin{aligned} {}\varphi(n)=&\varphi({p_1}^{k_1})\times\varphi({p_2}^{k_2})\times\cdots\times\varphi({p_r}^{k_r})\\ =&(p_1-1)\times {p_1}^{k_1-1}\times(p_2-1)\times{p_2}^{k_2-1}\times\cdots\times(p_r-1)\times{p_r}^{k_r-1}&\\ =&(p_1-1)\div p_1\times p_1^{k_1}\times(p_2-1)\div p_2\times p_2^{k_2}\times\cdots\times(p_r-1)\div p_r\times p_r^{k_r}&\\ =&n\times(p_1-1)\div p_1\times(p_2-1)\div p_2\times\cdots\times (p_r-1)\div p_r&\\ =&n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_r}) \end{aligned} $$

一些性质&定理

性质 1

设 $n$ 是一个大于 $2$ 的正整数，则所有与 $n$ 互质的数的和为 $\varphi(n)\div2\times n$。$\varphi(n)$ 为偶数。

性质 2

$\sum_{d|n}\varphi(d)=n$

欧拉定理

如果两个整数 $a$ 和 $b$ 互质，那么 $a^{\varphi(b)}\equiv1(mod\ n)$。

费马小定理

如果 $p$ 是一个质数，且 $a$ 不是 $p$ 的倍数，那么 $a^{p-1}\equiv1(mod\ p)$。

线性筛求欧拉函数

时间复杂度在 $O(n)$ 左右。

phi[1]=1;
for(int i=2;i<=n;i++)
{
    if(!flag[i])
    {
        phi[i]=i-1;
        p[++k]=i;
    }
    for(int j=1;p[j]*i<=n;j++)
    {
        flag[p[j]*i]=true;
        if(i%p[j]==0)
        {
            phi[i*p[j]]=phi[i]*p[j];
            break;
        } 
        else phi[i*p[j]]=phi[i]*(p[j]-1);
    }
}