杜教筛学习笔记

前置知识

狄利克雷卷积

若 $f\left(n\right)=\sum _{i\mid n}g\left(i\right)h\left(\frac{n}{i}\right)$f(n)=i∣n∑​g(i)h(in​)
则记 $f=g\ast h$f=g∗h

杜教筛

假如要求某积性函数 $f\left(n\right)$f(n) 的前缀和 (n<1012)。
假设另一个积性函数为 $g\left(n\right)$g(n)， $h=f\ast g$h=f∗g，记 $s\left(n\right)={\sum }_{i=1}^{n}f\left(i\right)$s(n)=i=1∑n​f(i)
则有 $\sum _{i=1}^{n}h\left(n\right)=\sum _{i=1}^n\sum _{j\mid i}g\left(j\right)f\left(\frac{i}{j}\right)=\sum _{j=1}^{n}g\left(j\right)\sum _{i=1}^{\lfloor \frac{n}{j}\rfloor }f\left(i\right)=\sum _{j=1}^{n}g\left(j\right)s\left(\lfloor \frac{n}{j}\rfloor \right)$i=1∑n​h(n)=i=1∑n​j∣i∑​g(j)f(ji​)=j=1∑n​g(j)i=1∑⌊jn​⌋​f(i)=j=1∑n​g(j)s(⌊jn​⌋)
然后把 $j=1$j=1 单独拎出来，有
$\sum _{i=1}^{n}h\left(n\right)=g\left(1\right)s\left(n\right)+\sum _{j=2}^{n}g\left(j\right)s\left(\lfloor \frac{n}{j}\rfloor \right)$i=1∑n​h(n)=g(1)s(n)+j=2∑n​g(j)s(⌊jn​⌋)
那么 $s\left(n\right)={\displaystyle \frac{{\sum }_{i=1}^{n}h\left(n\right)-{\sum }_{j=2}^{n}g\left(j\right)s\left(\lfloor {\displaystyle \frac{n}{j}}\rfloor \right)}{g\left(1\right)}}$s(n)=g(1)i=1∑n​h(n)−j=2∑n​g(j)s(⌊jn​⌋)​
如果 $h\left(n\right)$h(n) 可以快速求出来，我们就能很快求出 $s\left(n\right)$s(n)

下面举一些例子

求 i=1∑n​φ(n) (n<1011)
注意到 $n=\sum _{i\mid n}\phi \left(i\right)$n=i∣n∑​φ(i)，也就是 $Id=\phi \ast 1$Id=φ∗1
那么我们让 $h\left(n\right)=n$h(n)=n， $g\left(n\right)=1$g(n)=1
代入上式中，那就有
$s\left(n\right)={\displaystyle \frac{n\ast (n+1)}{2}}-{\sum }_{j=2}^{n}s\left(\lfloor {\displaystyle \frac{n}{j}}\rfloor \right)$s(n)=2n∗(n+1)​−j=2∑n​s(⌊jn​⌋)
然后 $\sqrt{n}$n ​ 枚举关键点 $j$j，递归求 $s\left(\lfloor {\displaystyle \frac{n}{j}}\rfloor \right)$s(⌊jn​⌋)
复杂度大概是 $O\left(n^{{\displaystyle \frac{3}{4}}}\right)$O(n43​)
为了加速，我们可以先线性预处理 $1e7$1e7 的前缀和
这样递归只用递归大于 $1e7$1e7 的关键点
然后对于大于 $1e7$1e7 的关键点，为了防止重复访问，我们采用记忆化，将 $x$x 这个点的值存在 $f\left[n/x\right]$f[n/x] 里面。
复杂度大概是 $O\left(n^{{\displaystyle \frac{2}{3}}}\right)$O(n32​)

一道模板题

洛谷 $p4213$p4213

代码如下

#include <bits/stdc++.h>
#define LL long long
#define N 3000005
using namespace std;
LL z = 1, sphi[N], t, smu[N], f[5005], g[5005];
int maxn = N - 5, cnt, n, p[N], x[N], mu[N], phi[N];
LL getphi(int x){
	int i, j;
	LL s = 0;
	unsigned l, r;
	if(x <= maxn) return sphi[x];
	if(f[n / x]) return f[n / x];
	for(l = 2; l <= x; l = r + 1){
		r = x / (x / l);
		s = s + (r - l + 1) * getphi(x / l);
	}
	f[n / x] = z * x * (x + 1) / 2 - s;
	return f[n / x];
}
LL getmu(int x){
	int i, j;
	LL s = 0;
	unsigned l, r;
	if(x <= maxn) return smu[x];
	if(g[n / x]) return g[n / x];
	for(l = 2; l <= x; l = r + 1){
		r = x / (x / l);
		s = s + (r - l + 1) * getmu(x / l);
	}
	g[n / x] = z - s;
	return g[n / x];
}
int main(){
	int i, j, T;
	mu[1] = phi[1] = 1;
	for(i = 2; i <= maxn; i++){
		if(!x[i]) x[i] = p[++cnt] = i, mu[i] = -1;
		for(j = 1; j <= cnt; j++){
			t = z * i * p[j];
			if(t > maxn) break;
			x[t] = p[j];
			if(i % p[j] == 0) break;
			mu[t] = -mu[i];
		}
	}
	for(i = 2; i <= maxn; i++){
		if(x[i / x[i]] == x[i]) phi[i] = phi[i / x[i]] * x[i];
		else phi[i] = phi[i / x[i]] * (x[i] - 1);
	}
	for(i = 1; i <= maxn; i++) sphi[i] = sphi[i - 1] + phi[i], smu[i] = smu[i - 1] + mu[i];
	scanf("%d", &T);
	while(T--){
		memset(f, 0, sizeof(f));
		memset(g, 0, sizeof(g));
		scanf("%d", &n);
		printf("%lld %lld\n", getphi(n), getmu(n));
	}
	return 0;
}