欧拉函数
定义
(1 sim N) 中与 (N) 互质的数的个数被成为欧拉函数, 记为 (varphi(N)).
若在算数基本定理中 (N=p_1^{c_1}p_2^{c_2} cdots p_k^{c_k}), 则
性质
性质一 (forall n>1), (1 sim n) 中与 (n) 互质的数的和为 (frac{n*varphi(n)}{2}).
证明: 因为 (gcd(n,x)=gcd(n,n-x)), 所以 (1 sim n) 中与 (n) 互质的数是成对存在的, 共有 (frac{varphi(n)}{2}) 对, 每一对的和为 (n), 总和便为 (frac{n*varphi(n)}{2}).
性质二 若 (gcd(a,b)=1) , 则 (varphi(ab)=varphi(a)varphi(b)).
证明: 由 (varphi(n)) 的计算式可得. 因此, 可以得到 (varphi(n)) 为积性函数.
积性函数
若当 (gcd(a,b)=1) 时, 有(f(ab)=f(a)f(b)), 则称函数 (f) 为积性函数.
性质三 若 (f) 是积性函数, 且在算数基本定理中 (n=Pi_{i=1}^{k}p_i^{c_i}), 则 (f(n)=Pi_{i=1}^{k}f(p_i^{c_i})).
性质四 若质数 (p|n), 且 (p^2|n), 则 (varphi(n)=varphi(frac{n}{p})*p).
证明: 因为 (p^2|n) , 所以 (n) 与 (frac{n}{p}) 的质因子种类无差别, 再由 (varphi(n)) 的计算式便可得到该性质.
性质五 若指数 (p|n), 但 (p^2 ot| n), 则 (varphi(n)=varphi(frac{n}{p})(p-1)).
证明: 因为 (p^2 ot| n), 所以 (frac{n}{p}) 与 (p) 互质, 所以 (varphi(n)=varphi(frac{n}{p})varphi(p)=varphi(frac{n}{p})(p-1)).
性质六 (sum_{d|n}varphi(d)=n).
证明: 设 (f(x)=sum_{d|x}varphi(d)), (gcd(i,j)=1), 则 (f(ij) =sum_{d|ij}varphi(d) =left( sum_{d|i}varphi(d) ight)*left( sum_{d|j}varphi(d) ight)=f(i)f(j).) 所以 (f) 为积性函数. 又因为 (f(p^c)=varphi(1)+varphi(p)+varphi(p^2)+cdots +varphi(p^c)=1+p-1+p(p-1)+cdots p^{c-1}(p-1)=p^c). (等比数列求和). 所以 (f(n)=Pi_{i=1}^{k}f(p_i^{k_i})=Pi_{i=1}^{k}p_i^{k_i}=n).
线性筛法
根据性质四和性质五, 可以类比质数的线性筛法得到 (varphi(n)) 的线性筛法.
void _phi(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!v[i]){ v[i]=i; pri[++pri[0]]=i; phi[i]=i-1; }
for(int j=1;j<=pri[0]&&pri[j]<=v[i]&&i*pri[j]<=n;j++){
v[i*pri[j]]=pri[j];
phi[i*pri[j]]= i%pri[j] ?phi[i]*(pri[j]-1) :phi[i]*pri[j];
}
}
}
例题
[POJ3090]Visible Lattice Points
欧拉反演
利用上文中的性质六 : (sum_{d|n}varphi(d)=n).
如 : 求 (sum_{i=1}^{n}gcd(i,n)).
将 (gcd(i,n)) 带入性质六的式子中,
就可以在 (sqrt n) 的时间内计算出答案.