杜教筛

我来填坑啦！（摘录自pengym大佬博客）

---

前置技能：

各种积性函数

• 我们平时所惯用的数论函数都是积性函数。
• 积性函数的定义：如果已知一个函数为数论函数，且$f(1)=1$f(1)=1，并且满足以下条件，若对于任意的两个互质的正整数$p,q$p,q都满足$f(p*q)=f(p)*f(q)$f(p∗q)=f(p)∗f(q)，那么称这个函数为积性函数。
• 特殊的，如果对于任意的正整数$p,q$p,q，也满足以上式子，则称这个函数为完全积性函数。
• 而本文的杜教筛，正是用来筛积性函数前缀和的一种神奇筛法！（当然比线性筛优秀啦）

常见积性函数

• μ$(n)$(n)–莫比乌斯函数。一会儿从另一种角度介绍它，顺便把上一节留的坑填一下。
• $\varphi(n)$φ(n)–欧拉函数。表示不大于n且与n互质的正整数个数。
• $d(n)$d(n)–约数个数。表示n的约数的个数。
• $\sigma(n)$σ(n)–约数和函数。即n的各个约数之和。表示为：$\sigma(n)=\sum_{d|n}d$σ(n)=∑d∣n​d。

（PS：接下来的是完全积性函数）

• $\epsilon(n)$ϵ(n)–元函数。$\epsilon(n)=[n=1]$ϵ(n)=[n=1]。
• $I(n)$I(n)–恒等函数。即对于所有的n，都为1。
• $id(n)$id(n)–单位函数。$id(n)=n$id(n)=n。

狄利克雷卷积（*）

基本知识

• 定义：两个数论函数$f$f和$g$g的卷积为$(f*g)(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$(f∗g)(n)=∑d∣n​f(d)∗g(dn​)。前面的括号代表将f卷g，后面的括号代表范围。
• 很显然，狄利克雷卷积满足以下运算规律：
  • 交换律；
  • 结合律；
  • 分配律；

（PS：积性函数*积性函数仍然为积性函数！）

莫比乌斯函数μ

• 在上一节，我们了解了一个性质：$\sum_{d|n}μ(d)=[n=1]$∑d∣n​μ(d)=[n=1]

• 我们将这个性质转化为卷积的形式，即：$μ*I=\epsilon$μ∗I=ϵ。这在狄利克雷卷积中是一个很常用的恒等式。有了它，我们就可以补一下上一次的坑了！

• 证明莫比乌斯反演：

  • 已知：

    $F(n)=\sum_{d|n}f(d)$F(n)=d∣n∑​f(d)

    用狄利克雷卷积表示，即：$F=f*I$F=f∗I。

    我们知道$I$I与μ函数卷起来有特殊性质:

    $F*μ=f*I*μ$F∗μ=f∗I∗μ

    通过结合律：

    $F*μ=f*(I*μ)=f*\epsilon=f$F∗μ=f∗(I∗μ)=f∗ϵ=f

    代入后得：$f(n)=\sum_{d|n}μ(d)*F(\frac{n}{d})$f(n)=∑d∣n​μ(d)∗F(dn​)。

    同理可以证明出另一种形式：$f(n)=\sum_{n|d}μ(\frac{d}{n})F(d)$f(n)=∑n∣d​μ(nd​)F(d)。

欧拉函数 φ

• φ。欧拉函数有一个性质，$\sum_{d|n}\varphi(d)=n$∑d∣n​φ(d)=n。

• 与上述方法类似，我们将它转化为狄利克雷卷积的形式：$\varphi*I=id$φ∗I=id。

• 这时候有一个大胆的想法，两边同时卷上μ，会有什么发现呢？

• 来填第二个坑，欧拉函数与莫比乌斯函数的关系。

  $\varphi*I*μ=id*μ$φ∗I∗μ=id∗μ

  $\varphi*\epsilon=id*μ$φ∗ϵ=id∗μ

  $\varphi(n)=id*u=\sum_{d|n}μ(d)*\frac{n}{d}$φ(n)=id∗u=d∣n∑​μ(d)∗dn​

  同时两边除以n，即：

  $\frac{\varphi(n)}{n}=\sum_{d|n}\frac{μ(d)}{d}$nφ(n)​=d∣n∑​dμ(d)​。

杜教筛

• 我们现在需要计算：$\sum_{i=1}^{n}f(i)$∑i=1n​f(i)，$f(i)$f(i)为积性函数。

• PS：接下来是杜教筛的套路式，latex打着太麻烦了，我就手写拍图好吧QAQ。

  

经过分析，只要当你的$h(i)$h(i)的前缀和很好求，能在较短时间内求出，那么我们对后面的式子进行整除分块，求S$(n)$(n)的复杂度为$O(n^{\frac{2}{3}})$O(n32​)。

筛欧拉函数

筛莫比乌斯函数

luoguP4213杜教筛模板

Coding

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define ll long long
using namespace std;
const int N=5e6+10;
int t,n,cnt,p[N],v[N],mu[N],phi[N],sum1[N];
ll sum2[N];
tr1::unordered_map<int,int>w;
tr1::unordered_map<int,ll>w1;
void get(int maxn){
    phi[1]=mu[1]=1;
    for(int i=2;i<=maxn;++i){
        if(!v[i]){
            p[++cnt]=i;mu[i]=-1;phi[i]=i-1;
        }
        for(int j=1;j<=cnt;++j){
            if(i*p[j]>maxn) break;
            v[i*p[j]]=p[j];
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            else mu[i*p[j]]=-mu[i],phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
    for(int i=1;i<=maxn;++i) sum1[i]=sum1[i-1]+mu[i],sum2[i]=sum2[i-1]+phi[i];
}
ll disphi(int N){
    if(N<=5000000) return sum2[N];
    if(w1[N]) return w1[N];
    ll ans=1LL*(1+N)*N/2;
    for(int l=2,r;l<=N;l=r+1){
        r=N/(N/l);
        ans-=1LL*disphi(N/l)*(r-l+1);
    }
    return w1[N]=ans;
}
int dismu(int N){
    if(N<=5000000) return sum1[N];
    if(w[N]) return w[N];
    int ans=1;
    for(int l=2,r;l>=0&&l<=N;l=r+1){
        r=N/(N/l);
        ans-=dismu(N/l)*(r-l+1);
    }
    return w[N]=ans;
}
int main(){
    scanf("%d",&t);
    get(5000000);
    while(t--){
        scanf("%d",&n);
        printf("%lld %d\n",disphi(n),dismu(n));
    }
    return 0;
}