之前学习了欧拉函数以及几个性质,知道了“欧拉函数 \varphi(n) 是小于或等于 n 的正整数中与 n 互质的数的数目。”对于求解单个的 \varphi(x) 很简单,直接枚举就可以了;但是如果要你在 \Theta (N) 时间复杂度内求 \varphi(i) 的值(i=1,2,\dots,n),怎么求呢?自然是用欧拉筛了~
几个性质
要用欧拉筛求解 1~N 的欧拉函数,需要用到几个性质:
- 欧拉函数是积性函数,即 \varphi(nm)=\varphi(n)\ast \varphi(m)。上次证明过。(其实是证明性质 3 要用)
-
当 p 为质数时,\varphi(p)=x-1。这条上次已经证明过。
-
对于质数 p,如果 p|i,那么 \varphi(i\ast p) = p \ast \varphi(i)。这个上次也证明过了。
-
对于质数 p,如果不满足 p|i,那么 \varphi(i\ast p) = (p-1) \ast \varphi(i)。这个要证明下……
一些证明
下面证明第三条性质:
因为 p 是质数而不满足 p|i,所以 p 与 i 互质,即 (p,i)=1。
根据性质 0,满足:\varphi(i \ast p)=\varphi(i)\ast \varphi(p)。
又根据性质 1,满足:\varphi(i \ast p)=\varphi(i)\ast (p-1)。得证。
求 1~N 的欧拉函数
首先复习一下欧拉筛:
inline void BuildPrime(){
vis[1]=false;
for (int i=2;i<=N;i++){
if (vis[i]) prime[++prime[0]]=i;
for (int j=1;j<=prime[0];j++){
if (i*prime[j]>N) break;
vis[i*prime[j]]=false;
if (i%prime[j]==0) break; // 如果再往后,prime[j] 就不是 i*prime[j] 的最小质因子了,所以不需要继续了
}
}
}
直接是枚举素数的。所以结合上面的性质,很容易得出求欧拉函数版的欧拉筛:
inline void BuildPhi(){
phi[1]=1;
memset(vis,1,sizeof(vis));
vis[1]=false;
for (int i=2;i<=N;i++){
if (vis[i]){
phi[i]=i-1;
prime[++prime[0]]=i;
}
for (int j=1;j<=prime[0];j++){
if (i*prime[j]>N) break;
vis[i*prime[j]]=false;
if (i%prime[j]) phi[i*prime[j]]=(prime[j]-1)*phi[i];
else {phi[i*prime[j]]=prime[j]*phi[i];break;}
}
}
}
本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://old.skywt.cn/posts/o-n-phi/