Dyd's Blog

He who has a strong enough why can bear almost any how.

杜教筛

Posted on In
Symbols count in article: 3.3k Reading time ≈ 3 mins.

亚线性筛法

前置

狄利克雷卷积

对于两个数论函数 $f, g$ ，其狄利克雷卷积就是 $(f * g)(n) = \sum_{d \mid n} f(d) * g(\frac{n}{d})$ ，显然，狄利克雷卷积卷积满足交换律、结合律、分配律

而常见的式子有：
$$
\mu * I = \epsilon \\
\varphi * I = id \\
\mu * id = \varphi \\
I * I = d \\
id * I = \sigma
$$
以上式子中，函数的定义如下：

  • $\mu$ ：莫比乌斯函数
  • $\varphi$ ：欧拉函数
  • $I$ ：恒等函数， $I(x) = 1$
  • $id$ ：单位函数 $id(x) = x$
  • $\epsilon$ ：元函数， $\epsilon(x) = [x == 1]$
  • $\sigma$ ：约数和函数， $\sigma(x) = \sum_{d \mid x} d$
  • $d$ ：约数个数函数， $d(x) = \sum_{d \mid x} 1$

下面如果未说明，函数的积定义为狄利克雷卷积

式子

很多时候，我们要对一个积性函数 $f$ 求前缀和，但这不好做到，如果我们可以构造一个积性函数 $g$ ，使得 $g, (f * g)$ 都比较好求，那么我们就可以在亚线性时间求出 $f$ 的前缀和；不妨记 $h = f * g$ ，$f$ 的前缀和为 $S$ ，开始推式子：
$$
\begin{aligned}
\sum_{i = 1}^n h(i)
& = \sum_{i = 1}^n \sum_{d \mid i} g(d) 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) \\
& = g(1)S(n) + \sum_{d = 2}^n g(d) S(\lfloor \frac{n}{d} \rfloor) \\
\end{aligned}
$$
于是：
$$
g(1)S(n) = \sum_{i = 1}^{n} h(i) - \sum_{d = 2}^n g(d) S(\lfloor \frac{n}{d} \rfloor)
$$
我们递归 + 记忆化计算 $S$ 即可

时间复杂度

那么问题来了，时间怎么分析？

先考虑数论分块的时间复杂度，我们有 $O(\sum_{i = 1}^n \frac{1}{\sqrt{i}}) = O(\sqrt{n})$

简证：
$$
\begin{aligned}
\frac{1}{\sqrt{i} + \sqrt{i + 1}} < & \frac{1}{2\sqrt{i}} < \frac{1}{\sqrt{i - 1} + \sqrt{i}} \\
\sqrt{i + 1} - \sqrt{i} < & \frac{1}{2\sqrt{i}} < \sqrt{i} - \sqrt{i - 1} \\
\sum_{i = 1}^{n} \sqrt{i + 1} - \sqrt{i} < &\sum_{i = 1}^{n} \frac{1}{2\sqrt{i}} < \sum_{i = 1}^{n} \sqrt{i} - \sqrt{i - 1} \\
\sqrt{n + 1} - 1 < & \frac{1}{2} \sum_{i = 1}^{n} \frac{1}{\sqrt{i}} < \sqrt{n} \\
\end{aligned}
$$
又因为 $\lfloor \frac{\lfloor \frac{n}{a}\rfloor}{b} \rfloor = \lfloor \frac{n}{ab} \rfloor$ ，加上记忆化每个 $S(\frac{n}{i})$ 恰被计算一次，而每个的复杂度为 $O(\sqrt{\frac{n}{i}})$ ，所以总时间为：
$$
\begin{aligned}
& O(\sum_{j = \frac{n}{i}} \sqrt{j}) \\
= & O(\sum_{j = 1}^{\sqrt{n}} \sqrt{\frac{n}{j}}) \\
= & O(\sqrt{n} \sum_{j = 1}^{\sqrt{n}} \frac{1}{\sqrt{j}}) \\
= & O(\sqrt{n} \sqrt{\sqrt{n}}) \\
= & O(n^{\frac{3}{4}})
\end{aligned}
$$
一个常用的优化是我们用线性筛预处理前 $k$ 项，复杂度为：
$$
\begin{aligned}
& O(k) + O(\sum_{j = \frac{n}{i} \wedge j > k} \sqrt{j}) \\
= & O(k) + O(\sum_{j = 1}^{\min(\sqrt{n}, \frac{n}{k})} \sqrt{\frac{n}{j}}) \\
= & O(k) + O(\sqrt{n} \sqrt{\min(\sqrt{n}, \frac{n}{k})}) \\
& 当 k < \sqrt{n} 时复杂度不变, 考虑 k \ge \sqrt{n} : \\
= & O(k + \frac{n}{\sqrt{k}})
\end{aligned}
$$
当 $k = n^{\frac{2}{3}}$ 时取得最优复杂度 $O(n^{\frac{2}{3}})$

代码

【模板】杜教筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using LL = long long;
const int NN = 1664510;
LL phi[NN];
int mu[NN], pri[NN], ct;
std::map<int, LL> Phi;
std::map<int, int> Mu;
bool vis[NN];
void prev()
{
    mu[1] = phi[1] = 1;
    for (int i = 2; i < NN; ++i)
    {
        if (!vis[i]) pri[++ct] = i, mu[i] = -1, phi[i] = i - 1;
        for (int j = 1; j <= ct && LL(i) * pri[j] < NN; ++j)
        {
            vis[i * pri[j]] = true;
            if (i % pri[j] == 0)
            {
                mu[i * pri[j]] = 0;
                phi[i * pri[j]] = phi[i] * pri[j]; 
                break;
            }
            mu[i * pri[j]] = -mu[i];
            phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
    for (int i = 2; i < NN; ++i) mu[i] += mu[i - 1], phi[i] += phi[i - 1];
}
LL calphi(int x)
{
    if (x < NN) return phi[x];
    if (Phi.find(x) != Phi.end()) return Phi[x];
    LL res = (LL(x) + 1) * x / 2;
    for (LL l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        res -= calphi(x / l) * (r - l + 1);
    }
    return Phi[x] = res;
}
int calmu(int x)
{
    if (x < NN) return mu[x];
    if (Mu.find(x) != Mu.end()) return Mu[x];
    int res = 1;
    for (LL l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        res -= calmu(x / l) * (r - l + 1);
    }
    return Mu[x] = res;
}
int main()
{
    prev();
    int T, n;
    for (scanf("%d", &T); T--; printf("%lld %d\n", calphi(n), calmu(n))) scanf("%d", &n);
    return 0;
}