埃氏筛

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

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

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

复杂度是 $n ·\sum \frac{1}{\text{prime}} = \mathcal{O}(n \log \log n) $

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

欧拉筛

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

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

由唯一分解定理，每个 $\ge 2$ 的整数可以唯一被分解为形如 $\prod _{i=1}^k{p}_i$ 的形式，其中 $p_1\ge p_2\ge \cdots \ge p_k，k\ge 1$.

于是我们考虑标记的时候只在当前的 $p$ 末尾加新的 $p_k+1$，即我们保证枚举的质数 $q\le pk$。

这样每个合数只会被枚举出来一次，因此复杂度是 $\mathcal{O}(n)$

积性函数

定义

若函数 $f(n)$ 满足 $f(1)=1$ 且 $\mathrm{\forall }x,y\in {\mathbf{N}}^{\ast },gcd(x,y)=1$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为积性函数。

若函数 $f(n)$ 满足 $f(1)=1$ 且 $\mathrm{\forall }x,y\in {\mathbf{N}}^{\ast }$ 都有 $f(xy)=f(x)f(y)$，则 $f(n)$ 为完全积性函数。

性质

若 $f(x)$ 和 $g(x)$ 均为积性函数，则以下函数也为积性函数：

$$\begin{array}{rl}h(x)& =f(x^p)\\ h(x)& =f^p(x)\\ h(x)& =f(x)g(x)\\ h(x)& =\sum _{d\mid x}f(d)g\left({\displaystyle \frac{x}{d}}\right)\end{array}$$

设 $x=\prod p_i^{k_i}$

若 $F(x)$ 为积性函数，则有 $F(x)=\prod F(p_i^{k_i})$。

若 $F(x)$ 为完全积性函数，则有 $F(x)=\prod F(p_i{)}^{k_i}$。

例子

• 单位函数：$\epsilon (n)=[n=1]$。(完全积性)
• 恒等函数：${\mathrm{id}}_k(n)=n^k$，${\mathrm{id}}_1(n)$ 通常简记作 $\mathrm{id}(n)$。(完全积性)
• 常数函数：$1(n)=1$。(完全积性)
• 除数函数：${\sigma }_k(n)=\sum _{d\mid n}{d}^k$。${\sigma }_0(n)$ 通常简记作 $d(n)$ 或 $\tau (n)$，${\sigma }_1(n)$ 通常简记作 $\sigma (n)$。
• 欧拉函数：$\phi (n)=\sum _{i=1}^n[gcd(i,n)=1]$
• 莫比乌斯函数：$\mu (n)=\{\begin{array}{ll}1& n=1\\ 0& \mathrm{\exists }d>1,d^2\mid n\\ (-1{)}^{\omega (n)}& \text{otherwise}\end{array}$，其中 $\omega (n)$ 表示 $n$ 的本质不同质因子个数，它是一个加性函数。

Dirichlet 卷积

定义

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

$$h(x)=\sum _{d\mid x}f(d)g\left({\displaystyle \frac{x}{d}}\right)=\sum _{ab=x}f(a)g(b)$$

上式可以简记为：

$$h=f\ast g$$

性质

交换律： $f\ast g=g\ast f$。

结合律：$(f\ast g)\ast h=f\ast (g\ast h)$。

分配律：$(f+g)\ast h=f\ast h+g\ast h$。

等式的性质： $f=g$ 的充要条件是 $f\ast h=g\ast h$，其中数论函数 $h(x)$ 要满足 $h(1)\ne 0$。

证明： 充分性是显然的。

证明必要性，我们先假设存在 $x$，使得 $f(x)\ne g(y)$。那么我们找到最小的 $y\in \mathbb{N}$，满足 $f(y)\ne g(y)$，并设 $r=f\ast h-g\ast h=(f-g)\ast h$。

则有：

$$\begin{array}{rl}r(y)& =\sum _{d\mid y}(f(d)-g(d))h\left({\displaystyle \frac{y}{d}}\right)\\ & =(f(y)-g(y))h(1)\\ & \ne 0\end{array}$$

则 $f\ast h$ 和 $g\ast h$ 在 $y$ 处的取值不一样，即有 $f\ast h\ne g\ast h$。矛盾，所以必要性成立。

证毕

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

证明： 设两个积性函数为 $f(x)$ 和 $g(x)$，再记 $h=f\ast g$。

设 $gcd(a,b)=1$，则：

$$h(a)=\sum _{d_1\mid a}f(d_1)g\left({\displaystyle \frac{a}{d_1}}\right),h(b)=\sum _{d_2\mid b}f(d_2)g\left({\displaystyle \frac{b}{d_2}}\right),$$

所以：

$$\begin{array}{rl}h(a)h(b)& =\sum _{d_1\mid a}f(d_1)g\left({\displaystyle \frac{a}{d_1}}\right)\sum _{d_2\mid b}f(d_2)g\left({\displaystyle \frac{b}{d_2}}\right)\\ & =\sum _{d\mid ab}f(d)g\left({\displaystyle \frac{ab}{d}}\right)\\ & =h(ab)\end{array}$$

所以结论成立。

证毕

例子

$$\begin{array}{rl}\epsilon =\mu \ast 1& ⟺\epsilon (n)=\sum _{d\mid n}\mu (d)\\ d=1\ast 1& ⟺d(n)=\sum _{d\mid n}1\\ \sigma =\mathrm{id}\ast 1& ⟺\sigma (n)=\sum _{d\mid n}d\\ \phi =\mu \ast \mathrm{id}& ⟺\phi (n)=\sum _{d\mid n}d\cdot \mu (\frac{n}{d})\\ \phi \ast 1& =\mathrm{id}\end{array}$$

莫比乌斯反演

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

莫比乌斯函数

$\mu$ 为莫比乌斯函数，定义为

$$\mu (n)=\{\begin{array}{ll}1& n=1\\ 0& n\text{含有平方因子}\\ (-1{)}^k& k\text{ 为 }n\text{ 的本质不同质因子个数}\end{array}$$

性质

$$\sum _{d\mid n}\mu (d)=\{\begin{array}{ll}1& n=1\\ 0& n\ne 1\end{array}$$

即

$$\sum _{d\mid n}\mu (d)=\epsilon (n)，\mu \ast 1=\epsilon$$

证明

设 ${\displaystyle n=\prod _{i=1}^k{p_i}^{c_i},n^{\prime }=\prod _{i=1}^k{p}_i}$

那么 ${\displaystyle \sum _{d\mid n}\mu (d)=\sum _{d\mid n^{\prime }}\mu (d)=\sum _{i=0}^k{\displaystyle (\genfrac{}{}{0ex}{}{k}{i})}\cdot (-1{)}^i=(1+(-1){)}^k}$

根据二项式定理，易知该式子的值在 $k=0$ 即 $n=1$ 时值为 $1$ 否则为 $0$，这也同时证明了 ${\displaystyle \sum _{d\mid n}\mu (d)=[n=1]=\epsilon (n)}$ 以及 $\mu \ast 1=\epsilon$

反演结论：${\displaystyle [gcd(i,j)=1]=\sum _{d\mid gcd(i,j)}\mu (d)}$

线性筛

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

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];
        }
    }
}

莫比乌斯变换

设 $f(n),g(n)$ 为两个数论函数。

形式一：如果有 $f(n)=\sum _{d\mid n}g(d)$，那么有 $g(n)=\sum _{d\mid n}\mu (d)f(\frac{n}{d})$。

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

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

形式二：如果有 $f(n)=\sum _{n|d}g(d)$，那么有 $g(n)=\sum _{n|d}\mu (\frac{d}{n})f(d)$。

例题

「SDOI2015」约数个数和

多组数据，求

$$\sum _{i=1}^n\sum _{j=1}^{m}d(i\cdot j)(n,m,T\le 5\times {10}^4)$$

其中 $d(n)=\sum _{i\mid n}1$，$d(n)$ 表示 $n$ 的约数个数

---

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

$$d(i\cdot j)=\sum _{x\mid i}\sum _{y\mid j}[gcd(x,y)=1]$$

再化一下这个式子

$$\begin{array}{rl}d(i\cdot j)=& \sum _{x\mid i}\sum _{y\mid j}[gcd(x,y)=1]\\ =& \sum _{x\mid i}\sum _{y\mid j}\sum _{p\mid gcd(x,y)}\mu (p)\\ =& \sum _{p=1}^{min(i,j)}\sum _{x\mid i}\sum _{y\mid j}[p\mid gcd(x,y)]\cdot \mu (p)\\ =& \sum _{p\mid i,p\mid j}\mu (p)\sum _{x\mid i}\sum _{y\mid j}[p\mid gcd(x,y)]\\ =& \sum _{p\mid i,p\mid j}\mu (p)\sum _{x\mid \frac{i}{p}}\sum _{y\mid \frac{j}{p}}1\\ =& \sum _{p\mid i,p\mid j}\mu (p)d\left(\frac{i}{p}\right)d\left(\frac{j}{p}\right)\end{array}$$

将上述式子代回原式

$$\begin{array}{rl}& \sum _{i=1}^n\sum _{j=1}^{m}d(i\cdot j)\\ =& \sum _{i=1}^n\sum _{j=1}^m\sum _{p\mid i,p\mid j}\mu (p)d\left(\frac{i}{p}\right)d\left(\frac{j}{p}\right)\\ =& \sum _{p=1}^{min(n,m)}\sum _{i=1}^n\sum _{j=1}^m[p\mid i,p\mid j]\cdot \mu (p)d\left(\frac{i}{p}\right)d\left(\frac{j}{p}\right)\\ =& \sum _{p=1}^{min(n,m)}\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }\mu (p)d(i)d(j)\\ =& \sum _{p=1}^{min(n,m)}\mu (p)\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }d(i)\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }d(j)\\ =& \sum _{p=1}^{min(n,m)}\mu (p)S\left(\lfloor \frac{n}{p}\rfloor \right)S\left(\lfloor \frac{m}{p}\rfloor \right)(S(n)=\sum _{i=1}^{n}d(i))\end{array}$$

那么 $O(n)$ 预处理 $\mu ,d$ 的前缀和，$O(\sqrt{n})$ 分块处理询问，总复杂度 $O(n+T\sqrt{n})$.

Code

// 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;
}