定义
φ ( n ) \varphi (n) φ(n)表示 [ 1 , n ] [1,n] [1,n]中与 n n n互质的数的个数。
性质
φ ( p ) = p − 1 , p ∈ P \varphi (p)=p-1,\ p\in \mathbb {P} φ(p)=p−1, p∈P
φ ( n ) = n ∏ i = 1 m p i − 1 p i \varphi (n)=n\prod_{i=1}^{m} \frac{p_i-1}{p_i} φ(n)=ni=1∏mpipi−1
线性筛（质数与欧拉函数）
void init()
{memset(isp,1,sizeof(isp));isp[1]=0;phi[1]=1;for(int i=2;i<N;i++){if(isp[i]){p[++np]=i;phi[i]=i-1;}for(int j=1;j<=np&&i*p[j]<N;j++){ll x=i*p[j];isp[x]=0;if(i%p[j]!=0)phi[x]=phi[i]*(p[j]-1);else {phi[x]=phi[i]*p[j];break;}}}
}
大众的方法
在一大坨式子中，枚举公因数 d d d。
例子
求 ∑ i = 1 n g c d ( i , n ) \sum _{i=1}^{n}gcd(i,n) i=1∑ngcd(i,n)
洛谷P2303 Longge的问题
考虑枚举公因数 d d d，因为显然的 1 ≤ d ≤ n 1 \le d \le n 1≤d≤n
那么原式转化为
∑ d ∣ n d ∑ i = 1 n [ g c d ( i , n ) = d ] \sum_{d|n}d\sum_{i=1}^{n}[gcd(i,n)=d] d∣n∑di=1∑n[gcd(i,n)=d]
艾弗森括号内除以 d d d
∑ d ∣ n d ∑ i = 1 n d [ g c d ( i , n d ) = 1 ] \sum_{d|n}d\sum_{i=1}^{\frac{n}{d}}\left[gcd\left(i,\frac {n}{d}\right)=1\right] d∣n∑di=1∑dn[gcd(i,dn)=1]
欧拉函数往里面一代
∑ d ∣ n d ⋅ φ ( n d ) \sum_{d|n}d \cdot \varphi \left(\frac{n}{d}\right) d∣n∑d⋅φ(dn)
