线性筛 | 欧拉筛

线性筛质数

每个数被最小的质因子筛一次。

int pn[N],cnt;
bool vis[N];
void pri(int n){vis[0]=vis[1]=1;
    for(int i=1;i<=n;i++){if(!vis[i])pn[++cnt]=i;
        for(int j=1;j<=cnt;j++){if(i*pn[j]>n)break;
            vis[i*pn[j]]=1;
            if(i%pn[j]==0)break;
        }
    }
}
  • 每次筛去 时, 是这个数的最小质因子
  • 如果 说明 有两个 的质因子,则再往后,i 中会有 的因子,而后面的 是大于 ,不是最小质因子,所以筛 一次就 break
  • 这三行代码顺序不能换。

积性函数

积性函数:对于任意互质的整数 a 和 b 有性质 的数论函数。

完全积性函数:对于任意整数 a 和 b 有性质 的数论函数。

常见积性函数

  • 欧拉函数
  • -莫比乌斯函数
  • -最大公因子,当 k 固定的情况
  • -n 的正因子数目(即
  • -n 的所有正因子之和
  • - 因子函数,n 的所有正因子的 k 次幂之和,当中 k 可为任何复数。
  • -幂函数,对于任何复数、实数 k,定义 (完全积性)

常见线性筛

线性筛欧拉函数

bool bp[N];
int p[N],cnt,phi[N];
void pri(int k){bp[0]=bp[1]=1;
    for(int i=2;i<=k;i++){if(bp[i]==0)p[++cnt]=i,phi[i]=i-1;
        for(int j=2;j<=cnt;j++){if(i*p[j]>k)break;
            bp[i*p[j]]=1;
            if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];
                    // 因为 p[j] 这个因子已经存在于 i 中,所以乘上以后,本来互质的仍然互质,本来不互质的仍然不互质。但是与它不互质的数有 p[j] 个倍数,所以与它互质的也多了 p[j] 倍。
                break;
            }
            phi[i*p[j]]=phi[i]*phi[p[j]];//i 和 p[j] 互质,利用积性函数的性质
        }
    }
}

线性筛莫比乌斯函数

bool bp[N];
int p[N],cnt,u[N];
void pri(int k){bp[0]=bp[1]=1,u[1]=1;
    for(int i=2;i<=k;i++){if(bp[i]==0)p[++cnt]=i,u[i]=-1;
        for(int j=2;j<=cnt;j++){if(i*p[j]>k)break;
            bp[i*p[j]]=1;
            if(i%p[j]==0){u[i*p[j]]=0;
                break;
            }
            u[i*p[j]]=-u[i];
        }
    }
}

线性筛约数个数

公式

​ 定义 表示 i 的最小质因子的次数。

bool bp[N];
int p[N],cnt,d[N],t[N];
void pri(int k){bp[0]=bp[1]=1,d[1]=1;
    for(int i=2;i<=k;i++){if(bp[i]==0)p[++cnt]=i,d[i]=2,t[i]=1;
        for(int j=2;j<=cnt;j++){if(i*p[j]>k)break;
            bp[i*p[j]]=1;
            if(i%p[j]==0){d[i*p[j]]=d[i]/(t[i]+1)*(t[i]+2),t[i*p[j]]=t[i]+1;// 多了一个因子
                break;
            }
            d[i*p[j]]=d[i]*d[p[j]],t[i*p[j]]=1;// 新的因子
        }
    }
}

线性筛约数和

公式

定义 t[i] 表示以 1 为首项,以 i 的最小质因子为公比,项数为 i 的次数的等比数列的和。

bool bp[N];
int p[N],cnt,sd[N],t[N];
void pri(int k){bp[0]=bp[1]=1,d[1]=1;
    for(int i=2;i<=k;i++){if(bp[i]==0)p[++cnt]=i,sd[i]=t[i]=i+1;
        for(int j=2;j<=cnt;j++){if(i*p[j]>k)break;
            bp[i*p[j]]=1;
            if(i%p[j]==0){t[i*p[j]]=t[i]*p[j]+1,sd[i*p[j]]=sd[i]/t[i]*t[i*p[j]];// 多了一个因子
                break;
            }
            sd[i*p[j]]=sd[i]*sd[p[j]],t[i*p[j]]=t[p[j]];// 新的因子
        }
    }
}

一般线性筛

对于一个积性函数 ,考虑以下的线性筛法:

  • 要计算 ,考虑到
  • 在线性筛的过程中,如果 ,就有 .
  • 否则,考虑 ,则有 .
  • 因此,我们只需要记录对于每一个 对应的 ,或者推导出从 的关系式即可

例题

表示有序三元组 的个数,使得 。求出 ~
n<=10^7

子问题 1-

  • 考虑枚举 a,b。 ;
  • 时间复杂度为
  • 总复杂度 .

题解

对 1~n 中的 x 分解质因数:

则一个质因数的幂的分配个数为:

乘法原理,f[x] 为:

容易证明,f 是一个积性函数。因为两个互质的数的质因子是不同的,所以乘在一起求积分别求积再相乘的结果是一样的,即当 时, 。证明如下:

  • 证明以后,线性筛积性函数即可。
    bool bp[N];
    int p[N],cnt,f[N],t[N];
    //f[i] 表示除了最小质因子幂的其他质因子幂的三元组排列方式;
    //t[i] 表示 i 的最小质因子的指数。
    void pri(int k){bp[0]=bp[1]=1;
      for(int i=2;i<=k;i++){if(bp[i]==0)p[++cnt]=i,f[i]=1,t[i]=1;
          for(int j=2;j<=cnt;j++){if(i*p[j]>k)break;
              bp[i*p[j]]=1;
              if(i%p[j]==0){f[i*p[j]]=f[i],t[i*p[j]]=t[i]+1;// 更新最小质因子幂
                  break;
              }
              f[i*p[j]]=f[i]*C(t[i]+2,2),t[i*p[j]]=1;
              // 乘上原来的最小质因子幂,然后让 p[j] 成为最小质因子
          }
      }
      for(int i=1;i<=n;i++)f[i]*=C(t[i]+2,2);// 把最小质因子幂乘回去
    }
    

  转载请注明: Sshwy's Blog 线性筛 | 欧拉筛

 上一篇
欧拉函数 | 欧拉定理 欧拉函数 | 欧拉定理
摘要 复习一下欧拉定理,顺便打了洛谷新出炉的模板~ 欧拉函数定义欧拉函数用希腊字母 表示, 表示 的欧拉函数。 的值为小于等于 且与 互质的数的
2018.11.16
下一篇 
状态压缩动态规划 状态压缩动态规划
引言状压 DP,是一种动态规划。一般的动态规划状态简单,通常一两个维度就能搞定。不过当状态过于复杂时,简单的维度将无法表示状态,而过多的维度将加大复杂度,于是,就有了状压 DP 的出现。 状态压缩状压 DP 的要点,就是状态压缩。状态压缩
2018.11.16
  目录