埃氏筛

基本思想是对于每个 的整数，把它们的非平凡倍数标记为不是质数。

埃氏筛法的流程大概是，我们从小到大考虑每个 ≥ 2 的整数，如果它没有标记则它是质数。

如果它是质数，我们把它的所有非平凡倍数标记为不是质数。

复杂度是

一个常数优化：对于一个质数 ，我们只用标记 的倍数。这并不改变复杂度。

欧拉筛

也被称为线性筛 (因为复杂度是线性)。

考虑从另一个方向优化标记，也就是对所有数考虑乘一个质数得到的新数。

由唯一分解定理，每个 的整数可以唯一被分解为形如 的形式，其中 ，.

于是我们考虑标记的时候只在当前的 末尾加新的 ，即我们保证枚举的质数 。

这样每个合数只会被枚举出来一次，因此复杂度是

积性函数

定义

若函数 满足 且 都有 ，则 为积性函数。

若函数 满足 且 都有 ，则 为完全积性函数。

性质

若 和 均为积性函数，则以下函数也为积性函数：

设

若 为积性函数，则有 。

若 为完全积性函数，则有 。

例子

  • 单位函数：。(完全积性)
  • 恒等函数：， 通常简记作 。(完全积性)
  • 常数函数：。(完全积性)
  • 除数函数：。 通常简记作 或 ， 通常简记作 。
  • 欧拉函数：
  • 莫比乌斯函数：，其中 表示 的本质不同质因子个数，它是一个加性函数。

Dirichlet 卷积

定义

对于两个数论函数 和 ，则它们的狄利克雷卷积得到的结果 定义为：

上式可以简记为：

性质

交换律： 。

结合律：。

分配律：。

等式的性质： 的充要条件是 ，其中数论函数 要满足 。

证明： 充分性是显然的。

证明必要性，我们先假设存在 ，使得 。那么我们找到最小的 ，满足 ，并设 。

则有：

则 和 在 处的取值不一样，即有 。矛盾，所以必要性成立。

证毕

两个积性函数的 Dirichlet 卷积也是积性函数

证明： 设两个积性函数为 和 ，再记 。

设 ，则：

所以：

所以结论成立。

证毕

例子

莫比乌斯反演

莫比乌斯反演是数论中的重要内容。对于一些函数 ，如果很难直接求出它的值，而容易求出其倍数和或约数和 ，那么可以通过莫比乌斯反演简化运算，求得 的值。

莫比乌斯函数

为莫比乌斯函数，定义为 含有平方因子为的本质不同质因子个数

性质

即 ，

证明

设

那么

根据二项式定理，易知该式子的值在 即 时值为 否则为 ，这也同时证明了 以及

反演结论：

线性筛

由于 函数为积性函数，因此可以线性筛莫比乌斯函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void getMu() {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!flg[i])
            p[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
            flg[i * p[j]] = 1;
            if (i % p[j] == 0) {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
}

莫比乌斯变换

设 为两个数论函数。

形式一：如果有 ，那么有 。

这种形式下，数论函数 称为数论函数 的莫比乌斯变换，数论函数 称为数论函数 的莫比乌斯逆变换（反演）。

容易看出，数论函数 的莫比乌斯变换，就是将数论函数 与常数函数 进行狄利克雷卷积。

形式二：如果有 ，那么有 。

例题

「SDOI2015」约数个数和

多组数据，求

其中 ， 表示 的约数个数

要推这道题首先要了解 函数的一个特殊性质

再化一下这个式子

将上述式子代回原式

那么 预处理 的前缀和， 分块处理询问，总复杂度 .

Code
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
// Date: 2023-07-30 13:22:17
// Problem: P3327 [SDOI2015] 约数个数和
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3327
// Memory Limit: 125 MB
// Time Limit: 1000 ms

......

constexpr int N = 50005;
int mu[N], pri[N], f[N], cnt;
bool st[N];

void init(){
    mu[1] = 1;
    F(i, 2, N) {
        if(!st[i]) pri[++ cnt] = i, mu[i] = -1;
        for(int j = 1; j <= cnt && i * pri[j] < N; ++j) {
            st[i * pri[j]] = 1;
            if(i % pri[j] == 0) {
                mu[i * pri[j]] = 0;
                break;
            }
            mu[i * pri[j]] = -mu[i];
        }
    }
    F(i, 1, N) mu[i] += mu[i - 1];
    F(i, 1, N) {
        for(int l = 1, r; l <= i; l = r + 1) {
            r = i / (i / l);
            f[i] += 1ll * (r - l + 1) * (i / l);
        }
    }
}

void solve(){
    int n, m;
    cin >> n >> m;
    if(n > m) swap(n, m);
    ll ans = 0;
    for(int l = 1, r; l <= n; l = r + 1){
        r = min(n / (n / l), m /(m / l));
                ans += 1ll * (mu[r] - mu[l - 1]) * f[n / l] * f[m / l];
        }
    cout << ans <<endl;
}

signed main(){
    fastio();
    int T;
    cin >> T;
    init();
    while(T--){
        solve();
    }
    return 0;
}