[笔记]杜教筛

dlstxdy!

杜教筛用于快速求数论函数的前缀和.当预处理了小于\(n^\frac{2}{3}\)的前缀和时,杜教筛的时间复杂度为\(O(n^\frac{2}{3})\)

形式化定义

给出数论函数\(f\),快速求\(S(n) = \sum_{i = 1}^nf(i)\)

解法

引理: \[ \sum_{i = 1}^n f \ast g (i) = \sum_{i = 1}^ng(i) \cdot S(\lfloor \frac{n}{i} \rfloor) \] 证明: $$ \[\begin{align} &\sum_{i = 1}^n f \ast g (i) \\ &= \sum_{i = 1}^n \sum_{d|n}f(d)\cdot g(\frac{n}{d})\\ &= \sum_{d = 1}^ng(d)\sum_{i*d = 1,d|i}^{i*d <= n}f(\frac{i}{d})\\ &= \sum_{d = 1}^ng(d)\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}f(i)\\ &= \sum_{d = 1}^ng(d)\cdot S(\lfloor \frac{n}{d} \rfloor) \end{align}\] \[ 观察上式,我们能得到: \] \[\begin{align} &g(1) \cdot S(n) \\ &= \sum_{i = 1}^ng(i) \cdot S(\lfloor \frac{n}{i} \rfloor) -\sum_{i = 2}^ng(i) \cdot S(\lfloor \frac{n}{i} \rfloor)\\ &= \sum_{i = 1}^n f \ast g(i) - \sum_{i = 2}^ng(i) \cdot S(\lfloor \frac{n}{i} \rfloor)\\ \end{align}\] $$ 这个式子的后半部分可以用数论分块递归去求,如果我们构造的\(g\)能快速求出\(\sum_{i = 1}^nf\ast g(i)\),我们就能快速求出\(g(1)\cdot S(n)\).

例子

筛\(\mu\)

我们知道\(\mu \ast 1 = \epsilon\)

因而有: \[ \begin{align} &1\cdot S(n) = S(n)\\ &= \sum_{i = 1}^n\mu \ast 1(i) - \sum_{i = 2}^n 1 \cdot S(\lfloor \frac{n}{i}\rfloor)\\ &= \sum_{i = 1}^n \epsilon - \sum_{i = 2}^n S(\lfloor \frac{n}{i}\rfloor)\\ &= 1 - \sum_{i = 2}^n S(\lfloor \frac{n}{i}\rfloor)\\ \end{align} \] 简单地把\(\mu \ast 1 = \epsilon\)带进上面的结论就行了.

代码:

(Mu为map,记忆化求过的μ.求之前先线性筛一遍小于maxn的μ.下面求φ同理)

注意\(g = 1\),减的时候别漏了(\(r-l+1\))=-=

ll du_mu(int x){
	if(x < maxn)return mu[x];
	else if(Mu[x])return Mu[x];
	ll tans = 1;
	for(int l = 2,r = 0;l <= x;l = r+1){
		r = x/(x/l);
		tans -= 1LL*(r - l + 1)*du_mu(x/l);
	}
	return Mu[x] = tans;
}

筛\(\varphi\)

和μ大同小异.我们有\(\varphi \ast 1 = id\),其中\(id(n) = n\) \[ \begin{align} &1\cdot S(n) = S(n)\\ &= \sum_{i = 1}^n\varphi \ast 1(i) - \sum_{i = 2}^n 1 \cdot S(\lfloor \frac{n}{i}\rfloor)\\ &= \sum_{i = 1}^n id(i) - \sum_{i = 2}^n S(\lfloor \frac{n}{i}\rfloor)\\ &= \frac{n*(n+1)}{2} - \sum_{i = 2}^n S(\lfloor \frac{n}{i}\rfloor)\\ \end{align} \] 代码:

ll du_phi(int x){
	if(x < maxn)return phi[x];
	else if(Phi[x])return Phi[x];
	ll tans = 1LL*x*(x+1)/2;
	for(int l = 2,r = 0;l <= x;l = r+1){
		r = x/(x/l);
		tans -= 1LL*(r-l+1)*du_phi(x/l);
	}
	return Phi[x] = tans;
}