杜教筛

博主： spirit
发布时间：2021 年 08 月 04 日
2540 次浏览
暂无评论
4875字数
分类：数论

# 杜教筛

刚开始学习杜教筛，把一些用到的重要性质记一下，方便以后复习。

## 一、积性函数

### 1.定义

1. 定义在所有正整数上的函数为数论函数（算术函数）。
2. 如果一个数论函数 $f$ 对于任意两个互质的正整数 $p$ 和 $q$ ，都有 $f(pq) = f(p)f(q)$ ，称 $f$ 为积性函数。
3. 如果对于任意的两个正整数 $p$ 和 $q$ 都有上述性质，则称 $f$ 为完全积性函数。

### 2.性质

如果 $f$ 是积性函数，那么 $f$ 的和函数 $F(n) = \sum_{d | n} f(d)$ 也是积性函数。证明比较简单，略过。

### 3.常见的积性函数

$I(n)$ ：恒等函数，$I(n) = 1$

$id(n)$ ：单位函数，$id(n)  = n$

$I_k(n)$ ：幂函数，$I_k(n) = n^k$

$\epsilon (n)$ ：元函数，$\epsilon(n) = \begin{cases} 1, n = 1\\ 0,  n > 1\end{cases}$

$\sigma(n)$ ：因子和函数，$\sigma(n) = \sum_{d | n} d$

$d(n)$ ：约数个数，$d(n) = \sum_{d | n} 1$

## 二、欧拉函数

### 1.性质

1. 欧拉函数是积性函数，由通解公式可证明。
2. 设 $n$ 为正整数，那么 $\sum_{d | n} \phi(d) = n$ 。
   
   证明：考虑分数 $\frac{1}{n}, \frac{2}{n}, ... , \frac{n}{n}$ 共 $n$ 个，且互不相同。将这些分数化简到最简形式，得到新的 $n$ 个形如 $\frac{a}{d}$ 的分数，其中 $a, d$ 互质且 $d | n$ 。在新的 $n$ 个分数中，分母为 $d$ 的数量为 $\phi(d)$ 。所有分母的总数就是 $\sum_{d | n} \phi(d)$ ，因此原式得证。

## 三、数论分块

对于一个整数 $l$ ，满足 $\lfloor \frac{n}{r} \rfloor = \lfloor \frac{n}{l} \rfloor$ 的最大的 $r$ 取值为 $r = n / (n / l)$  。

证明：设 $\lfloor \frac{n}{l} \rfloor = k$ ，可以写为 $kl + p = n$ ，$1 \leq p < l$ 。设 $\lfloor \frac{n}{l + d} \rfloor = k$ ，则有 $k(l + d) + p' = n$ 。可得 $p' = p - kd$ ，则 $d$ 的最大值为 $\lfloor \frac{p}{k} \rfloor$ ，化简得：

$$
\begin{equation}\begin{split}
r &= l + d_{max}\\
&= l + \lfloor \frac{p}{k} \rfloor \\
&= l + \lfloor \frac{n - kl}{k} \rfloor \\
&= \lfloor l + \frac{n - kl}{k} \rfloor \\
&= \lfloor \frac{kl}{k} + \frac{n - kl}{k} \rfloor \\
&= \lfloor \frac{n}{k} \rfloor \\
&= \lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor \\
\end{split}\end{equation}
$$

## 四、狄利克雷卷积

### 1.定义

设 $f, g$ 为数论函数，记 $f$ 和 $g$ 的狄利克雷卷积为 $f * g$ ，定义为：

$$
(f * g)(n) = \sum_{d | n} f(d)g(\frac{n}{d})
$$

### 2. 性质

1. 交换律：$f*g = g * f$
2. 结合律：$(f * g) * h = f * (g * h)$
3. 分配律：$f * (g + h) = (f * g) + (f * h)$
4. 元函数：$\epsilon(n) = \begin{cases} 1, n = 1 \\ 0, n > 1 \end{cases}$ ，对任何 $f$ ，有 $e * f = f * e = f$
5. 两个积性函数的狄利克雷卷积仍然是积性函数

有关性质的证明可以参考[算法学习笔记(35): 狄利克雷卷积](https://zhuanlan.zhihu.com/p/137619492)

## 五、莫比乌斯函数与莫比乌斯反演

### 1.定义

定义参考[数论进阶——莫比乌斯反演](https://blog.rclouds.top/archives/17/)

### 2.性质

$$
\sum_{d | n} \mu(d) = 
\begin{cases} 
1, n = 1 \\
0, n > 1 \\
\end{cases}
$$

证明：

1. $n = 1$ 时，显然有 $\mu(1) = 1$ 。
2. $n > 1$ 时，设 $n$ 有 $m$ 个不同的质因子，则：
   
   $$
   \sum_{d | n} \mu(d) = C_m^0 - C_m^1 + C_m^2 - ...... = \sum_{i = 0}^m (-1)^iC_m^i = 0
   $$

## 六、杜教筛

### 1. 杜教筛公式

问题：设 $f$ 是一个积性函数，计算 $S(n) = \sum_{i =  1}^{n} f(i)$ 。

杜教筛的思路是：构造一个与 $f(n)$ 有关的能够使用数论分块的新函数，达到快速求解 $S(n)$ 的目的。

构造两个积性函数 $h$ 和 $g$ ，满足 $h = g * f$ ，根据定义：

$$
\begin{equation}\begin{split}
\sum_{i = 1}^n h(i) &= \sum_{i = 1}^n \sum_{d | i} g(d) f(\frac{i}{d}) \\
&= \sum_{d = 1}^n g(d) \sum_{d | i} f(\frac{i}{d}) \\
&= \sum_{d = 1}^n g(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} f(i) \\
&= \sum_{d = 1}^n g(d) S(\lfloor \frac{n}{d} \rfloor) \\
\end{split}\end{equation}
$$

我们把最后一个式子的第一项提出来，可以得到：

$$
g(1)S(n) = \sum_{i = 1}^n h(i) - \sum_{i = 2}^n g(i)S(\lfloor \frac{n}{i} \rfloor) \\
$$

如果上式中 $h, g$ 函数的前缀和可以很轻松的求出来，就可以使用数论分块处理 $S(\lfloor \frac{n}{i} \rfloor)$ ，达到快速求 $S(n)$ 的目的。

### 2.杜教筛时间复杂度

求 $h, g$ 函数的速度很大程度上取决于如何构造这两个函数，因此先将这两个函数忽视掉。设求 $S(n)$ 的时间复杂度为 $T(n)$ ，由数论分块可知 $\lfloor \frac{n}{i} \rfloor$ 只有 $2 \sqrt n$ 个取值，可得：

$$
\begin{equation}\begin{split}
T(n) &= O(\sqrt n) + \sum_{i = 1}^{\sqrt n} (T(i) + T(\frac{n}{i})) \\
&= O(\sqrt n) + O(\int_{1}^{\sqrt n} (\sqrt i + \sqrt \frac{n}{i})) \\
&= O(n^{\frac{3}{4}}) \\
\end{split}\end{equation}
$$

上式中的 $T(i)$ 和 $T(\frac{n}{i})$ 之所以只展开一次是因为展开后其他的部分是高阶小量，可以忽略掉，证明方法仿照上式再展开一次求积分即可。

如果我们先预处理好 $S(n)$ 的前 $m$ 项，该时间复杂度一般为 $O(m)$ ，则整体的时间复杂度为：

$$
\begin{equation}\begin{split}
&O(m) + T(n) \\
&= O(m) + \sum_{i = 1}^{\lfloor \frac{n}{m} \rfloor} T(\frac{n}{i}) \\
&= O(m) + O(\int_1^{\lfloor \frac{n}{m} \rfloor} \sqrt \frac{n}{i}) \\
&= O(m) + O(\frac{n}{\sqrt m}) \\
\end{split}\end{equation}
$$

易得当 $m = n^{\frac{2}{3}}$ 时，时间复杂度取得最小值 $O(n^{\frac{2}{3}})$ 。

### 3.求欧拉函数与莫比乌斯函数的前缀和

[luogu P4213](https://www.luogu.com.cn/problem/P4213)

由欧拉函数的性质可知：$n = \sum_{d | n} \phi(d)$ ，可取 $h(n) = id(n)$ ，$g(n) = I(n)$ ，$f(n) = \phi(n)$ 。

由莫比乌斯函数的性质：$\sum_{d | n} \mu(d) = \begin{cases} 1, n = 1 \\ 0, n > 1 \\ \end{cases}$ ，取 $h(n) = \epsilon(n)$ ，$g(n) = I(n)$ ，$f(n) = \mu(n)$ 。

然后先用线性筛预处理，再使用杜教筛求解即可。代码如下：

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 5e6 + 7;

int primes[N + 10], cnt;
bool prime[N + 10];
int mu[N + 10];
LL phi[N + 10];
unordered_map<int, int> summu;
unordered_map<int, LL> sumphi;

void init() {
	cnt = 0;
	mu[1] = 1;
	phi[1] = 1;
	prime[0] = prime[1] = true;
	for (int i = 2; i < N; i++) {
		if (!prime[i]) {
			primes[cnt++] = i;
			phi[i] = i - 1;
			mu[i] = -1;
		}
		for (int j = 0; primes[j] <= N / i; j++) {
			prime[i * primes[j]] = true;
			if (i % primes[j]) {
				mu[i * primes[j]] = -mu[i];
				phi[i * primes[j]] = phi[i] * phi[primes[j]];
			} else {
				mu[i * primes[j]] = 0;
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			}
		}
	}
	for (int i = 1; i < N; i++) {
		mu[i] += mu[i - 1];
		phi[i] += phi[i - 1];
	}
}

int get_smu(int n) {
	if (n < N) return mu[n];
	if (summu.count(n)) return summu[n];
	LL ans = 1;
	for (LL l = 2, r; l <= n; l = r + 1) {
		r = min((LL)n, n / (n / l));
		ans -= (r - l + 1ll) * get_smu(n / l);
	}
	return summu[n] = ans;
}

LL get_sphi(int n) {
	if (n < N) return phi[n];
	if (sumphi.count(n)) return sumphi[n];
	LL ans = n * (n + 1ll) / 2;
	for (LL l = 2, r; l <= n; l = r + 1) {
		r = min((LL)n, n / (n / l));
		ans -= (r - l + 1ll) * get_sphi(n / l);
	}
	return sumphi[n] = ans;
}

int main() {
	init();
	int T, n;
	cin >> T;
	while (T --) {
		scanf("%d", &n);
		printf("%lld %d\n", get_sphi(n), get_smu(n));
	}
	return 0;
}
```

最后修改：2021 年 08 月 04 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

杜教筛

spirit • 2021 年 08 月 04 日

# 杜教筛

刚开始学习杜教筛，把一些用到的重要性质记一下，方便以后复习。

## 一、积性函数

### 1.定义

### 2.性质

如果 $f$ 是积性函数，那么 $f$ 的和函数 $F(n) = \sum_{d | n} f(d)$ 也是积性函数。证明比较简单，略过。

### 3.常见的积性函数

$I(n)$ ：恒等函数，$I(n) = 1$

$id(n)$ ：单位函数，$id(n)  = n$

$I_k(n)$ ：幂函数，$I_k(n) = n^k$

$\epsilon (n)$ ：元函数，$\epsilon(n) = \begin{cases} 1, n = 1\\ 0,  n > 1\end{cases}$

$\sigma(n)$ ：因子和函数，$\sigma(n) = \sum_{d | n} d$

$d(n)$ ：约数个数，$d(n) = \sum_{d | n} 1$

## 二、欧拉函数

### 1.性质

## 三、数论分块

对于一个整数 $l$ ，满足 $\lfloor \frac{n}{r} \rfloor = \lfloor \frac{n}{l} \rfloor$ 的最大的 $r$ 取值为 $r = n / (n / l)$  。

## 四、狄利克雷卷积

### 1.定义

设 $f, g$ 为数论函数，记 $f$ 和 $g$ 的狄利克雷卷积为 $f * g$ ，定义为：

$$
(f * g)(n) = \sum_{d | n} f(d)g(\frac{n}{d})
$$

### 2. 性质

有关性质的证明可以参考[算法学习笔记(35): 狄利克雷卷积](https://zhuanlan.zhihu.com/p/137619492)

## 五、莫比乌斯函数与莫比乌斯反演

### 1.定义

定义参考[数论进阶——莫比乌斯反演](https://blog.rclouds.top/archives/17/)

### 2.性质

$$
\sum_{d | n} \mu(d) = 
\begin{cases} 
1, n = 1 \\
0, n > 1 \\
\end{cases}
$$

证明：

## 六、杜教筛

### 1. 杜教筛公式

问题：设 $f$ 是一个积性函数，计算 $S(n) = \sum_{i =  1}^{n} f(i)$ 。

杜教筛的思路是：构造一个与 $f(n)$ 有关的能够使用数论分块的新函数，达到快速求解 $S(n)$ 的目的。

构造两个积性函数 $h$ 和 $g$ ，满足 $h = g * f$ ，根据定义：

我们把最后一个式子的第一项提出来，可以得到：

$$
g(1)S(n) = \sum_{i = 1}^n h(i) - \sum_{i = 2}^n g(i)S(\lfloor \frac{n}{i} \rfloor) \\
$$

如果上式中 $h, g$ 函数的前缀和可以很轻松的求出来，就可以使用数论分块处理 $S(\lfloor \frac{n}{i} \rfloor)$ ，达到快速求 $S(n)$ 的目的。

### 2.杜教筛时间复杂度

上式中的 $T(i)$ 和 $T(\frac{n}{i})$ 之所以只展开一次是因为展开后其他的部分是高阶小量，可以忽略掉，证明方法仿照上式再展开一次求积分即可。

如果我们先预处理好 $S(n)$ 的前 $m$ 项，该时间复杂度一般为 $O(m)$ ，则整体的时间复杂度为：

易得当 $m = n^{\frac{2}{3}}$ 时，时间复杂度取得最小值 $O(n^{\frac{2}{3}})$ 。

### 3.求欧拉函数与莫比乌斯函数的前缀和

[luogu P4213](https://www.luogu.com.cn/problem/P4213)

由欧拉函数的性质可知：$n = \sum_{d | n} \phi(d)$ ，可取 $h(n) = id(n)$ ，$g(n) = I(n)$ ，$f(n) = \phi(n)$ 。

由莫比乌斯函数的性质：$\sum_{d | n} \mu(d) = \begin{cases} 1, n = 1 \\ 0, n > 1 \\ \end{cases}$ ，取 $h(n) = \epsilon(n)$ ，$g(n) = I(n)$ ，$f(n) = \mu(n)$ 。

然后先用线性筛预处理，再使用杜教筛求解即可。代码如下：

```cpp
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 5e6 + 7;

int primes[N + 10], cnt;
bool prime[N + 10];
int mu[N + 10];
LL phi[N + 10];
unordered_map<int, int> summu;
unordered_map<int, LL> sumphi;

int main() {
	init();
	int T, n;
	cin >> T;
	while (T --) {
		scanf("%d", &n);
		printf("%lld %d\n", get_sphi(n), get_smu(n));
	}
	return 0;
}
```

杜教筛

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Kattis Message （状态机模型 + 矩阵快速幂）

数论进阶——莫比乌斯反演

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

Kattis Fruit Slicer （计算几何 + 扫描线）

Kattis Fruit Slicer （计算几何 + 扫描线）

计算几何基础知识

SDUT 2020 Autumn Team Contest---44

SDUT 2020 Autumn Team Contest---43(for 19)

堆的实现

杜教筛

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

杜教筛

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款