欧拉函数杂记
定义
φ ( 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)
