学习笔记 - 杜教筛

不知道为什么以前会学自闭……

---

# 引入

线性筛可以 $O(n)$ 筛出积性函数的值，从而得到前 $n$ 项积性函数的前缀和。

但是在一些数论题目中（比如莫比乌斯反演）要求解 $n$ 更大的积性函数前缀和。我们仍然采用筛法，但需要复杂度低于线性的、专门筛积性函数前缀和的筛法——杜教筛。

---

# 前置

• 莫比乌斯函数 & 欧拉函数
• 狄利克雷卷积

---

# 杜教筛

实际上，对于任意数论函数 $f(x)$，设其前缀和为 $S(x)$，有

$$\sum_{i=1}^n(f\ast g)(i)=\sum_{i=1}^ng(i)S\left(\left\lfloor\frac ni\right\rfloor\right)$$

证明

直接推式子：

$$ \begin{aligned} \sum_{i=1}^n(f\ast g)(i)&=\sum_{i=1}^n\sum_{d\mid i}g(d)f\left(\frac id\right)\\ &=\sum_{d=1}^ng(d)\sum_{d\mid i}f\left(\frac id\right)\\ &=\sum_{d=1}^ng(d)\sum_{k=1}^{\left\lfloor\frac nd\right\rfloor}f(k)\\ &=\sum_{d=1}^ng(d)S\left(\left\lfloor\frac nd\right\rfloor\right)\\&&\square \end{aligned} $$

对上述结论变形，提取出等式右侧的 $i=1$：

$$\begin{aligned} \sum_{i=1}^n(f\ast g)(i)&=\sum_{i=2}^ng(i)S\left(\left\lfloor\frac ni\right\rfloor\right)+g(1)S(n)\\ g(1)S(n)&=\sum_{i=1}^n(f\ast g)(i)-\sum_{i=2}^ng(i)S\left(\left\lfloor\frac ni\right\rfloor\right) \end{aligned}$$

这就是杜教筛的主要式子，第一个求和式可以数论分块，而第二个求和式结合该函数性质求解。

这就要求对所求的 $f(x)$ 找到合适的函数 $g(x)$。

---

# $\mu(x)$ 前缀和

选取 $g=\mathbf1$（常函数），则有 $\mu\ast\mathbf1=\varepsilon$。

$$\begin{aligned} \mathbf{1}(1)S(n)&=\sum_{i=1}^n\varepsilon(i)-\sum_{i=2}^n\mathbf1(i)S\left(\left\lfloor\frac ni\right\rfloor\right)\\ S(n)&=1-\sum_{i=2}^nS\left(\left\lfloor\frac ni\right\rfloor\right) \end{aligned}$$

复杂度不会证……直接算的复杂度是 $O(n^{\frac34})$，但是下标极大，记忆化要map/unordered_map，常数极大；一般会预处理 $n$ 较小（$\le n^{\frac23}$，但是实际上我的做法是“能够线性筛筛出来的就筛”）的前缀和，直接线性筛，然后复杂度就会降到 $O(n^{\frac23})$，常数一般。

---

# $\varphi(x)$ 前缀和

用到 $\varphi$ 的性质：$\varphi\ast\mathbf1=\text{id}$（$\text{id}(x)=x$）。

仍然取 $g=\mathbf1$，则有

$$\begin{aligned} \mathbf1(1)S(n)&=\sum_{i=1}^n\text{id}(i)-\sum_{i=2}^n\mathbf1(i)S\left(\left\lfloor\frac ni\right\rfloor\right)\\ S(n)&=\frac{n(n+1)}2-\sum_{i=2}^nS\left(\left\lfloor\frac ni\right\rfloor\right) \end{aligned}$$

跟筛 $\mu(x)$ 的前缀和差不多，也要预处理前面较小的 $n$ 的前缀和。

但是一般不用杜教筛筛 $\varphi(x)$，因为可以直接莫比乌斯反演。

点击展开/折叠 莫比乌斯反演$\varphi(x)$前缀和

$$\sum_{i=1}^n\varphi(i)=\sum_{i=1}^n\sum_{j=1}^i[\gcd(i,j)=1]$$

即求 $i,j\in[1,n]$ 且 $i,j$ 互质的无序数对 $(i,j)$ 数量。转化一下，改为求有序数对 $(i,j)$ 的数量，即求：

$$ \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\\ =&\sum_{d=1}^n\mu(d)\left\lfloor\frac nd\right\rfloor^2 \end{aligned} $$

需要杜教筛算 $\mu$ 的前缀和，以及数论分块。

---

# 源代码

> Linked 例题 洛谷 P4213

/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;

inline int Read(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r;
}

typedef long long ll;
const int N=2e6;

bool vis[N];
int prm[N/10],smu[N],nprm;
unordered_map<int,ll> memphi,memmu;

ll KeyMu(int n){ //杜教筛-莫比乌斯函数
	if(n<N) return smu[n];
	if(memmu.count(n)) return memmu[n];
	memmu[n]=1;
	for(int i=2;i<=n;i++){
		int j=(n/(n/i));
		memmu[n]-=KeyMu(n/i)*(j-i+1);
		i=j;
	}
	return memmu[n];
}
ll KeyPhi(int n){ //杜教筛-欧拉函数
	if(n<0) return 0;
	if(n==1) return 1;
	if(memphi.count(n)) return memphi[n];
	memphi[n]=n*(n+1ll)/2;
	for(int i=2;i<=n;i++){
		int j=(n/(n/i));
		memphi[n]-=KeyPhi(n/i);
		i=j;
	}
	return memphi[n];
}
ll FliPhi(int n){ //莫比乌斯反演-欧拉函数
	ll ret=0;
	for(int i=1;i<=n;i++){
		int j=(n/(n/i));
		ret+=(KeyMu(j)-KeyMu(i-1))*(n/i)*(n/i);
		i=j;
	}
	return ((ret-1)>>1)+1;
}
int main(){
	smu[1]=1;
	for(int i=2;i<N;i++){
		if(!vis[i]) smu[prm[++nprm]=i]=-1;
		for(int j=1;j<=nprm && 1ll*prm[j]*i<N;j++){
			vis[prm[j]*i]=true;
			if(i%prm[j]==0) break;
			smu[prm[j]*i]=-smu[i];
		}
	}
	for(int i=1;i<N;i++) smu[i]+=smu[i-1];
	int cas=Read();
	while(cas--){
		int n=Read();
		printf("%lld %lld\n",FliPhi(n),KeyMu(n));
	}
	return 0;
}

---

THE END

Thanks for reading!

$$\begin{split} “\ &像旅行的风\ 将时间带走\\ &我的心中那沉闷到底为谁拥有\\ &向着天空\ 伸出了手\\ &我多么希望再一次对你说\ ”\\ ——&\text{《404 Not Found》By 赤羽} \end{split}$$

> Linked 404 Not Found-Bilibili