定义

欧拉函数$\varphi(x)$表示不大于$x$的与$x$互质的正整数的数量。特别的，$\varphi(1)=1$。 $$ \begin{align*} & \varphi(n)=n\frac{\prod_{i=1}^k(p_i-1)}{\prod_{i=1}^kp_i},p_i为n的质因子 \end{align*} $$

性质

1.

若$p$是质数，则$\varphi(p^n)=p^{n-1}(p-1)$。

$$ \begin{align*} & 证明:\ & 在不大于p^n的正整数中，不与之互质的只有p的倍数: p,2p,3p,…p^{n-1}\cdot p,共p^{n-1}个\ & ，所以\varphi(x)=p^n-p^{n-1}\ & \ & 证毕. \end{align*} $$

2.

若$ a|x $，则$\varphi(ax)=a\varphi(x)$ $$ \begin{align*} & 证明:\ & 设\varphi(x)个整数分别为d_1,d_2,d_3\cdots d_{\varphi(x)},由于a|x,这些数也和a互质。所以当a>1,\ &则d_1+x,d_2+x,\cdots ,d_{\varphi(x)}+x也小于ax并与之互质。当a>2，同理，d_1+x,\ &d_2+x,\cdots ,d_{\varphi(x)}+x也小于ax并与之互质。一共有a组，所以共有a组，\varphi(ax)=a\varphi(x)\ & 证毕. \end{align*} $$

3.

若$a,b$互质，则$\varphi(a)\varphi(b)=\varphi(ab)$

$$ \begin{align*} & 证明:\ & 设a=p_1\times p_2 \times \cdots p_k,b = p_{k+1} \times p_{k+2}\times\cdots p_{k+m}\ & 带入公式\ & \varphi(a)=a\frac{(p_1-1)(p_2-1)\cdots (p_k-1)}{p_1p_2p_3\cdots p_k}\ & \varphi(b)=b\frac{(p_{k+1}-1)(p_{k+2}-1)\cdots (p_{k+m}-1)}{p_{k+1}p_{k+2}p_{k+3}\cdots p_{k+m}}\ & 两式相乘\ & \varphi(a)\cdot\varphi(b)=ab\frac{(p_1-1)(p_2-1)\cdots(p_{k+m}-1)}{p_1p_2p_3\cdots p_{k+m}}\ & 因为a,b互质，p_{1-k}和p_{k+1,k+m}无相等值，所以上式=\varphi(ab)\ & 证毕. \end{align*} $$

代码

既然公式都有了，那代码就很好写了

1
2
3
4
5
6
7
8

int phi(int n){
    int res = n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)(res/=i)*=(i-1);
        while(n%i==0)n/=i;
    }
    if(n>1)(res/=n)*(n-1);
}

复杂度$O(\sqrt n)$

可以用筛法来求

1
2
3
4
5
6
7

int phi[MAXN];
void Init(int n){
    for(int i=1;i<=n;i++)phi[i]=i;
    for(int i=2;i<=n;i++)
        if(phi[i]==i)
            for(int j=i;j<=n;j+=i)phi[j]=phi[j]/i*(i-1);
}

复杂度$O(n \log \log n)$

还可以优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int phi[MAXN],np[MAXN],primes[MAXN],m;
void Init(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!np[i])primes[++m]=i,phi[i]=i-1;//性质一
        for(int j=1;j<=m;j++){
            int p = primes[j];
            if(p*i>n)break;
            np[p*i]=1;
            if(i%p==0)phi[p*i]=phi[i]*p;//性质二
            else phi[p*i]=phi[p]*phi[i];//性质三 
        }
    }
}

这种做法用到了上面的三种性质，复杂度为$O(n)$。