SkyWT / 博客 / 欧拉筛的应用:在线性时间(O(N))内求出 1~N 的欧拉函数

欧拉筛的应用:在线性时间(O(N))内求出 1~N 的欧拉函数

2018 年 8 月 9 日 08:53


文章目录

之前学习了欧拉函数以及几个性质,知道了“欧拉函数 φ(n)\varphi(n) 是小于或等于 nn 的正整数中与 nn 互质的数的数目。”对于求解单个的 φ(x)\varphi(x) 很简单,直接枚举就可以了;但是如果要你在 Θ(N)\Theta (N) 时间复杂度内求 φ(i)\varphi(i) 的值(i=1,2,,ni=1,2,\dots,n),怎么求呢?自然是用欧拉筛了~

几个性质

要用欧拉筛求解 1~N 的欧拉函数,需要用到几个性质:

  1. 欧拉函数是积性函数,即 φ(nm)=φ(n)φ(m)\varphi(nm)=\varphi(n)\ast \varphi(m)。上次证明过。(其实是证明性质 3 要用)

  2. pp 为质数时,φ(p)=x1\varphi(p)=x-1。这条上次已经证明过。

  3. 对于质数 pp,如果 pip|i,那么 φ(ip)=pφ(i)\varphi(i\ast p) = p \ast \varphi(i)。这个上次也证明过了。

  4. 对于质数 pp,如果不满足 pip|i,那么 φ(ip)=(p1)φ(i)\varphi(i\ast p) = (p-1) \ast \varphi(i)。这个要证明下……

一些证明

对于第一条性质和第二条性质, 都证明过了;

下面证明第三条性质:

因为 pp 是质数而不满足 pip|i,所以 ppii 互质,即 (p,i)=1(p,i)=1
根据性质 0,满足:φ(ip)=φ(i)φ(p)\varphi(i \ast p)=\varphi(i)\ast \varphi(p)
又根据性质 1,满足:φ(ip)=φ(i)(p1)\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;}
        }
    }
}

暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)