笔者太菜，现在才学欧拉函数还学得不咋滴……

定义

定义：$φ(n)$是小于等于$n$，且与$n$互质的数的个数。

写成另一个式子就是：$∑_{i=1}^{n} 1[gcd(i,n)==1]$

有一个结论，是$φ(n)$为积性函数，即有$φ(ab)=φ(a)*φ(b)$.

还有一些其它性质：当$p$为质数时，显然有$φ(p)=p-1$.

若$p|n$ 且$p^2 | n$,则$φ(n)=φ(n/p)*p$

若$p|n$ 且不满足$p^2 | n$，则$φ(n)=φ(n/p)*(p-1)$

还有：$∑_{d|n} φ(d)=n$

由于它是积性函数，于是我们可以用欧拉筛把它筛出来。

当$p=prime$时，用第一个性质。

当$p$与$x$互质时，则$φ(x*p)=φ(x)*φ(p)$

当$x$与$p$不互质时，就有：

设$x=t*p^k$

则有：$φ(x*p)=φ(t*p^{k+1})=φ(t*p^k)*p=φ(x)*p$

由此可以写出欧拉筛程序：

void Init(){
    phi[1]=1;
    for(int i=2;i<=MAXN;++i){
        if(is_prime[i])phi[i]=i-1,p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;++j){
            is_prime[i*p[j]]=0;
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            else phi[i*p[j]]=phi[i]*phi[p[j]];
        }
    }
}

继续普及定理：

欧拉定理：当$x$与$p$互质时，有：

$x^{φ(m)}≡1(mod p)$

这个东西的局限性有点大，来看一下拓展欧拉定理：

无需$x$与$p$互质，当$y>φ(p)$时，有：

$ x^y$ $≡$ $x^{b%φ(p)+φ(p)}$ $(mod p)$

当$y<φ(p)时，指数上没有那个+φ(p)

根据这个东西，我们可以解决一些问题，诸如：

$2^{2^{2^...}}$ $mod$ $p$的东西（上帝与集合的正确用法）

来一个题目：求$x,y<=n$且$gcd(x,y)∈prime$的数对个数。

看向文章第一个式子，$∑_{i=1}^{n} 1[gcd(i,n)==1]$

自然联想到欧拉函数。

把$gcd$变一下，$gcd(x,y)=1$ $->$ $gcd(x*p,y*p)=p(p∈prime)$

那么，我们就想求$p∈prime$ 且$p<=n$

自然一遍筛法。而且可以顺便把欧拉函数筛出来。

对于一个数对$(a,b)$,设$a<=b$,

那么$a$有$varphi(p)$个值可以使$gcd(a,b)=1$.

那么我们可以做一下前缀和。

答案就变为：枚举所有$p<=n$且p为质数，由于没有大小限制所以最后答案$*2$;注意枚举时的重复，注意欧拉函数统计1时所计算的重复，所以有$-1$.

$Code:$

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=1e7+10;
int phi[MAXN],n,tot,p[MAXN],flg[MAXN];
long long Ans,sum[MAXN];
void Init(int MAXN1){
    phi[1]=1;
    /*for(int i=2;i<=MAXN1;++i){
        if(!phi[i])
            prime[++tot]=i;
            for(int j=i;j<=MAXN1;j+=i){
                if(!phi[j])phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
    }*/
    phi[1]=1;
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            } else {
                phi[i*p[j]]=phi[i]*phi[p[j]];
            }
        }
    }
    for(int i=1;i<=MAXN;++i)sum[i]=sum[i-1]+phi[i];
}
int main(){
    scanf("%d",&n);
    Init(n+10);
    for(int i=1;i<=tot&&p[i]<=n;++i)Ans+=sum[n/p[i]]+sum[n/p[i]]-1;
    printf("%lld\n",Ans);
    return 0;
}

欧拉

浅谈欧拉函数

定义