标签：lfloor limits dfrac sum rfloor 杜教 mu

1 积性函数和狄利克雷卷积

1.1 积性函数

1.1.1 定义

积性函数在以前的学习中遇到过很多，例如莫比乌斯函数 \(\mu(n)\)，欧拉函数 \(\varphi(n)\) 等等。那么我们对积性函数定义如下：

称定义域在正整数上的函数叫做数论函数（也叫算数函数）。
对于一个数论函数 \(f(n)\)，如果 \(f(xy)=f(x)f(y)\) 对于任意互质的 \(x,y\in\mathbb{N}_+\) 都成立，则称 \(f(n)\) 为积性函数。
特别的，对于一个数论函数 \(f(n)\)，如果 \(f(xy)=f(x)f(y)\) 对于任意的 \(x,y\in\mathbb{N}_+\) 都成立，则称 \(f(n)\) 为完全积性函数。

1.1.2 常见积性函数

单位函数：\(\varepsilon(n)=[n=1]\)（完全积性）。
恒等函数：\(\text{id}_k(n)=n^k\)（完全积性）。其中 \(\text{id}_1(n)=n\)，通常简记为 \(\text{id}(n)\)。
常数函数：\(1(n)=1\)（完全积性）。
除数函数：\(\sigma_k(n)=\sum\limits_{d\mid n} d^k\)。其中 \(\sigma_0(n)\) 即因子个数，通常简记为 \(d(n)\)；\(\sigma_1(n)\) 即因子之和，通常简记为 \(\sigma(n)\)。
欧拉函数：\(\varphi(n)=\sum\limits_{i=1}^n[\gcd(i,n)=1]\)。
莫比乌斯函数：\(\mu(n)\)。

1.2 狄利克雷卷积

1.2.1 定义

对于两个数论函数 \(f(x)\) 与 \(g(x)\)，它们的狄利克雷卷积得到的结果 \(h(x)\) 定义为：

\[h(x)=\sum_{d\mid x} f(d)g(\dfrac xd) \]

上式通常简记为：

\[h=f*g \]

例如在 \(1.1.2\) 中出现的一些函数，我们会有如下式子：

\(\varepsilon=\mu*1\)。
\(d=1*1\)。
\(\sigma=\text{id}*1\)。
\(\varphi=\mu*\text{id}\)。

1.2.2 性质

交换律：\(f*g=g*f\)。
结合律：\((f*g)*h=f*(g*h)\)。
分配率：\((f+g)*h=f*h+g*h\)。

2 杜教筛

2.1 引入

首先需要了解的前置知识：积性函数、狄利克雷卷积、数论分块。

杜教筛处理的是对于一类数论函数 \(f(n)\)，求其前缀和 \(S(n)=\sum\limits_{i=1}^nf(i)\) 的值。通常情况下 \(n\) 会很大，所以线性复杂度是不可行的。我们考虑数论分块，假如我们能够构造一个 \(S(n)\) 关于 \(S(\lfloor\dfrac ni\rfloor)\) 的递推式，就可以用数论分块快速求解了。

2.2 算法思想

对于一个数论函数 \(g\)，会有如下等式：

\[\begin{aligned} \sum_{i=1}^n (f*g)(i)=&\sum_{i=1}^n\sum_{d\mid i}g(d)f(\dfrac i d)\\ =&\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac ni\rfloor}g(i)f(j)\\ =&\sum_{i=1}^ng(i)\sum_{j=1}^{\lfloor\frac ni\rfloor}f(j)\\ =&\sum_{i=1}^ng(i)S(\lfloor\dfrac ni\rfloor) \end{aligned} \]

于是会有如下递推式：

\[\begin{aligned} g(1)S(n)=&\sum_{i=1}^n g(i)S(\lfloor\dfrac ni\rfloor)-\sum_{i=2}^n g(i)S(\lfloor\dfrac ni\rfloor)\\ =&\sum\limits_{i=1}^n(f*g)(i)-\sum_{i=2}^n g(i)S(\lfloor\dfrac ni\rfloor) \end{aligned} \]

假如我们可以构造适当的函数 \(g\)，使得：

可以快速求解出 \(\sum\limits_{i=1}^n (f*g)(i)\)。
可以快速求解出 \(g(i)\) 的前缀和，以便后面使用数论分块求解 \(\sum\limits_{i=2}^n g(i)S(\lfloor\dfrac ni\rfloor)\)。

我们就能在较短时间内求得 \(g(1)S(n)\)。

具体来讲，杜教筛的时间复杂度是 \(O(n^{3/4})\) 的。如果我们可以快速求出前 \(n^{2/3}\) 项的函数值（例如使用线性筛），就可以降低复杂度至 \(O(n^{2/3})\)。值得注意的是，这个时间复杂度是基于记忆化搜索的，因此需要使用 map 等数据结构存储下 \(S(i)\) 的值。

2.3 实例

例 1：【模板】杜教筛。

题意：求 \(\sum\limits_{i=1}^n\varphi(i)\) 和 \(\sum\limits_{i=1}^n \mu(i)\)。

先考虑求 \(S_1(n)=\sum\limits_{i=1}^n \mu(i)\)。

根据狄利克雷卷积可知，\(\varepsilon=\mu*1\)，所以直接构造 \(g(n)=1(n)\) 即可，于是：

\[\begin{aligned} S_1(n)=&\sum\limits_{i=1}^n \mu(i)\\ =&\sum\limits_{i=1}^n \varepsilon(i)-\sum\limits_{i=2}^n1(i)S_1(\lfloor\dfrac ni\rfloor)\\ =&1-\sum\limits_{i=2}^nS_1(\lfloor\dfrac ni\rfloor) \end{aligned} \]

然后考虑求 \(S_2(n)=\sum\limits_{i=1}^n\varphi(i)\)，实际上这个用莫比乌斯反演更容易得出，最后可以转化为求 \(\mu\) 的前缀和。不过我们同样可以使用杜教筛求解。

关于欧拉函数有一个广为人知的性质：\(\sum\limits_{d\mid n}\varphi(d)=n\)，即 \(\varphi*1=\text{id}\)。通过这个也就可以证明出上文提到的 \(\varphi=\mu*\text{id}\) 的结论了。

我们仍然构造 \(g(n)=1(n)\)，于是：

\[\begin{aligned} S_2(n)=&\sum\limits_{i=1}^n \varphi(i)\\ =&\sum\limits_{i=1}^n \text{id}(i)-\sum\limits_{i=2}^n1(i)S_2(\lfloor\dfrac ni\rfloor)\\ =&\dfrac{n(n+1)}2-\sum\limits_{i=2}^nS_2(\lfloor\dfrac ni\rfloor) \end{aligned} \]

代码如下：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define int long long

using namespace __gnu_pbds;
using namespace std;

const int Maxn = 2e6 + 5;
const int Inf = 2e9;

int T;
int n;

int prim[Maxn], cnt, mu[Maxn], phi[Maxn];
bool vis[Maxn];

const int N = 2e6;
void init() {
	mu[1] = 1;
	phi[1] = 1;
	for(int i = 2; i <= N; i++) {
		if(!vis[i]) {
			prim[++cnt] = i;
			mu[i] = -1;
			phi[i] = i - 1;
		}
		for(int j = 1, x; j <= cnt && (x = prim[j] * i) <= N; j++) {
			vis[x] = 1;
			if(i % prim[j] == 0) {
				mu[x] = 0;
				phi[x] = phi[i] * prim[j];
				break;
			}
			mu[x] = -mu[i];
			phi[x] = phi[i] * (prim[j] - 1);
		}
	}
	for(int i = 1; i <= N; i++) {
		mu[i] += mu[i - 1];
		phi[i] += phi[i - 1];
	}
}

gp_hash_table <int, int> smu, sphi;

int sum_mu(int x) {
	if(x <= N) return mu[x];
	if(smu[x]) return smu[x];
	int l = 2, r = 0, res = 1;
	while(l <= x) {
		r = x / (x / l);
		res -= sum_mu(x / l) * (r - l + 1);
		l = r + 1;
	}
	return smu[x] = res;
}

int sum_phi(int x) {
	if(x <= N) return phi[x];
	if(sphi[x]) return sphi[x];
	int l = 2, r = 0, res = (x + 1) * x / 2;
	while(l <= x) {
		r = x / (x / l);
		res -= sum_phi(x / l) * (r - l + 1);
		l = r + 1;
	}
	return sphi[x] = res;
}

void solve() {
	cin >> n;
	cout << sum_phi(n) << " " << sum_mu(n) << '\n';
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	init();
	while(T--) solve();
	return 0;
}

例 2：[CQOI2015] 选数。

题意： 求出在值域区间 \([L,H]\) 中选出 \(n\) 个数且它们的 \(\gcd\) 恰为 \(k\) 的方案数。

这是经典 \(\gcd\) 容斥了，设 \(f(x)\) 表示选出的 \(n\) 个数的 \(\gcd\) 是 \(x\) 的倍数的方案数，\(g(x)\) 表示选出的 \(n\) 个数的 \(\gcd\) 恰为 \(x\) 的方案数。容易得到：

\[f(x)=\sum_{x\mid d}g(d) \]

根据莫比乌斯反演可得：

\[g(x)=\sum_{x\mid d}\mu(\dfrac dx)f(d) \]

根据定义，我们又知道 \(f(x)=(\lfloor\dfrac R x\rfloor-\lceil\dfrac Lx\rceil+1)^n=(\lfloor\dfrac R x\rfloor-\lfloor\dfrac {L-1}x\rfloor)^n\)，所以我们就可以轻松得出：

\[g(x)=\sum_{x\mid d}\mu(\dfrac dx)(\lfloor\dfrac R d\rfloor-\lfloor\dfrac {L-1}d\rfloor)^n \]

但是发现这个式子无法通过数论分块去优化复杂度，因此需要另辟蹊径。考虑在原始的 \(g(x)\) 式子中不去枚举 \(d\)，转而去枚举 \(\dfrac dx\)，可以得到：

\[\begin{aligned} g(x)=&\sum_{i=1}^{\lfloor\frac Rk\rfloor}\mu(i)f(ki)\\ =&\sum_{i=1}^{\lfloor\frac Rk\rfloor}\mu(i)(\lfloor\dfrac R {ki}\rfloor-\lfloor\dfrac {L-1}{ki}\rfloor)^n \end{aligned} \]

令 \(R'=\lfloor\dfrac Rk\rfloor,L'=\lfloor\dfrac {L-1}{k}\rfloor\)，则：

\[g(x)=\sum_{i=1}^{R'}\mu(i)(\lfloor\dfrac {R'} {i}\rfloor-\lfloor\dfrac {L'}{i}\rfloor)^n \]

此时整个式子就可以数论分块求解了，但是此时发现线性求 \(\mu\) 的前缀和复杂度仍然会炸，所以使用杜教筛求其前缀和即可。

标签：lfloor,limits,dfrac,sum,rfloor,杜教,mu
From： https://www.cnblogs.com/UKE-Automation/p/18580436

杜教筛