狄利克雷卷积到筛法

前置符号

$$[P] = \begin{cases} 1,&\text{if the proposition } P \text{ is true}\\ 0,&\text{if the proposition } P \text{ is false} \end{cases}$$

集合的表示：
$$S = \{x:P\}$$
表示满足条件 $P$ 的 $x$ 构成的集合

数论函数与狄利克雷卷积

指一类函数：其定义域为 $\mathbb N^*$，值域为某个数集。

两个数论函数的加法:
$$(f+g)(n) = f(n) + g(n)$$
逐项相加即可。

数乘：
$$(cf)(n) = c(f(n))$$
两个数论函数的狄利克雷卷积（用 $*$ 表示）：
$$\begin{aligned} (f*g)(n) &= \sum_{d\mid n}f(d)\times g\left(\frac n d\right)\\ &= \sum_{d_1 \times d_2 = n}f(d_1)\times f(d_2) \end{aligned}$$
注意狄利克雷卷积其实就是关于乘法的卷积（$d_1d_2=n$）。

其具有如下性质：

1. 交换律：$f*g = g*f$，乘法满足交换律，得证。

2. 结合律：$(f*g)*h=f*(g*h)$：
   $$\sum_{(ij)k = n}(f(i)g(j))h(k)=\sum_{i(jk) = n}f(i)(g(j)h(k))$$

3. 对加法的分配律：$(f+g)*h = f*h + g*h$：
   $$\begin{aligned} &(f(n) + g(n)) * h(n)\\ =&\sum_{d\mid n}(f(d) + d(d))h\left(\frac nd\right)\\ =&\sum_{d\mid n}f(d)h\left(\frac nd\right) + \sum_{d\in n}g(d)h\left(\frac nd\right)\\ =&f(n)*h(n) + g(n)*h(n) \end{aligned}$$

4. 与数乘的结合律：$(cf)*g = c(f*g)$

5. 单位元：$\epsilon * f = f$，$\epsilon(n) = [n = 1]$。即这个单位元函数当 $n = 1$ 时返回 $1$，当 $n\not=1$ 时返回 $0$。
   $$\begin{aligned} f * \epsilon &= \sum_{d\mid n} f(d)\epsilon\left(\frac nd\right) \end{aligned}$$
   不难验证其正确性：只有当 $d = n$ 时 $\epsilon(n/d)$ 才等于 $1$，只保留了 $f(n)$ 这一项。

6. 狄利克雷逆元：$f^{-1}*f=\epsilon$。考虑如何求这个逆元：
   $$\begin{aligned} \epsilon &= f^{-1}*f\\ \epsilon &= \sum_{d\mid n}f^{-1}(d)f\left(\frac nd\right)\\ \epsilon(n) &= f^{-1}(n)f(1) + \sum_{d\mid n\land d < n} f^{-1}(d)f\left(\frac nd\right)\\ f^{-1}(n) &=\frac1{f(1)}\left(\epsilon(n) – \sum_{d\mid n\land d < n} f^{-1}(d)f\left(\frac nd\right)\right) \end{aligned}$$
   于是这个逆元就被求出来了。不难发现只要 $f$ 满足 $f(1)\not=0$，其就会具有逆元

狄利克雷卷积就是研究函数的乘法结构

容斥原理到莫比乌斯反演

首先我们有算术基本定理
$$n=\prod_{k = 1}^{\omega(n)} p_k^{a_k}$$
注意到此时 $\omega(n)$ 描述了一个数 $n$ 的约数种类数

定义欧米茄函数
$$\Omega(n) = \sum_{k = 1}^{\omega(n)} a_k$$
它描述了一个数约数的总个数。

有了如上定义，我们就可以引入莫比乌斯函数了：
$$\mu(n) = 1^{-1}(n) = [\omega(n) =\Omega(n)]\times (-1)^{\omega(n)}$$
其中 $1$ 的意义为常函数 $f(n) = 1$。

分析一下这个神奇的定义：

• 首先，此处定义莫比乌斯函数为 $1$ 的逆元，注意到其具有如下性质
  $$\sum_{d\mid n}\mu(d) = \begin{cases} 1,&n = 1\\ 0,&n\not= 1 \end{cases}$$
  证明：设 $n' = \displaystyle\prod_{k=1}^{\omega}p_k$，不难发现
  $$\sum_{d\mid n}\mu(d) = \sum_{d\mid n'}\mu(d) = \sum_{k = 0}^\omega \binom{\omega}{k}(-1)^k = (1 + (-1))^\omega$$
  根据二项式定理，发现 $\omega = 0$ 即 $n = 1$ 时式子为 $1$，否则为 $0$。

  所以我们知道 $\mu*1 = \epsilon$

• 其次，分析后面的那坨式子：

  • $\omega(n) = \Omega(n)$ 如果不成立，说明整个函数值就为 $0$ 了。即 $n$ 具有平方因子
  • 如果 $n = 1$，则显然 $\mu(1) = 1$
  • 如果 $\omega(n) = \Omega(n)$ 成立，那么函数的值即取决于函数具有奇数个还是偶数个质因子，前者 $-1$，后者 $1$

很重要的一点：
$$\mathrm{id}^k * t = \epsilon$$
其中 $\mathrm{id}^k(n) = n^k$， $t(n) = \mu(n)n^k$

简证：
$$\begin{aligned} &(\mathrm{id}^k*t)(n)\\ =&\sum_{d\mid n}d^k\mu\left(\frac n d\right)\left(\frac nd\right)^k\\ =&n^k\sum_{d\mid n}\mu\left(\frac n d\right)\\ =&n^k\epsilon(n)\\ =&\epsilon(n) \end{aligned}$$
还有：$\phi = \mu * \mathrm{id}$，简证：
$$\begin{aligned} &(\mu*\mathrm{id})(n)\\ =&\sum_{d\mid n}\mu(d)\left(\frac nd\right)\\ =&\sum_{d\mid n}\mu\left(\frac nd\right)d\\ =&\sum_{d = 1}^n[d\mid n]\mu\left(\frac nd\right)d\\ \end{aligned}$$

再来看看容斥原理：
$$\left|\bigcup_{i=1}^nS_i\right|=\sum_{T\subseteq\{1,2,\cdots,n\}}(-1)^{|T| – 1}\left|\bigcap_{j\in T}S_j\right|$$
其描述的就是多个集合的并内的元素个数应该如何计算。

证明：考虑一个任意一个元素 $x$ 在 $k$ 个集合 $S_i$ 中，则在选取的时候：

• 选取集合个数为 $1$ 时，这个元素被加了 $k$ 次
• 选取集合个数为 $2$ 时，这个元素被减了 $\displaystyle\binom k 2$ 次，因为一共是存在 $\displaystyle\binom k 2$ 种选法使得选出的两个集合内包含 $x$
• 选取集合个数为 $3$ 时，这个元素又被加了 $\displaystyle\binom k 3$ 次
• 选取集合个数为 $4$ 时，这个元素被减了 $\displaystyle\binom k 4$ 次
• ……

总的来看，元素 $x$ 对答案产生的贡献即为
$$\sum_{i = 1}^k \binom k i\times(-1)^{i + 1}$$
由二项式定理知其结果为 $1$，所以每个元素都正正好好被统计了一次，命题得证。

回到刚才的唯一分解式
$$n=\prod_{k = 1}^{\omega(n)} p_k^{a_k}$$
我们将容斥原理换一种方式表达：
$$(-1)^0\times \bigcup_{k = 1}^{\omega}A_i + \sum_{k = 1}^\omega\left((-1)^k\times\sum_{1\le j_1< j_2 <\cdots <j_k\le \omega}\left(\bigcap_{p = 1}^kA_{j_p}\right) \right)= \varnothing$$
定义
$$f(a) = \prod_{k}^\omega p_k^{[a\in A_k]}$$

$$B_{\frac nd} = \{a:d\mid f(a)\}$$

其中 $d\mid n$

理解一下上面的式子：$A_k$ 表示好多好多个集合，其中 $A_k$ 被染色成了唯一分解式中的 $p_k$，然后 $A_{k_1}\cap A_{k_2}$ 被染成了 $p_{k_1}\times p{k_2}$，依次类推。不难发现 $f(a)$ 即代表了一个元素所在区域的颜色（如下图）

而 $B_{\frac nd}$ 表示的就是图中的一个划分。举个例子：$n = p_{k_1}^{a_{k_1}}p_{k_2}^{a_{k_2}}p_{k_3}^{a_{k_3}}$（对应上面的图），当 $d = p_{k_1}p_{k_2}$ 时，满足 $d \mid f(a)$ 的也只有上图绿色的两块区域了，所以 $B_{\frac n d} = A_{k_1}\cap A_{k_2}$

有了上述定义，我们有下面的式子：
$$\sum_{d\mid n}(\mu(d)\times B_{\frac nd}) = \varnothing$$
发现其具有的就是容斥原理的形式。

进一步地，我们定义
$$\begin{aligned} g\left(\frac n d\right) &= \{a:d = f(a)\} \end{aligned}$$
所以有
$$(1*g)\left(\frac nd\right) = \{a:d\mid f(a)\}$$

$$\varnothing = g = \mu * 1 * g = \sum_{d\mid n}\left(\mu(d)\times(1*g)\left(\frac nd\right)\right)$$

联系上述式子尽量理解其含义

最终，莫比乌斯反演的表达式是如下的：
$$\begin{aligned} g(n) = \sum_{d\mid n}f(d) & \iff f(n) = \sum_{d\mid n}\left(\mu(d)\times g\left(\frac nd\right) \right)=\sum_{d\mid n}\left(g(d)\times \mu\left(\frac nd\right) \right)\\ g = 1 * f&\iff f = \mu * g \end{aligned}$$
莫比乌斯反演的本质就是容斥原理

例题：洛谷P3455 [POI2007]ZAP-Queries

题意：求
$$\sum_{i = 1}^a\sum_{j = 1}^b[\gcd(i,j) = d]$$
解：

莫比乌斯反演时，一般要将含 $\gcd$ 的式子化为 $\gcd(i,j) = 1$ 的形式才好反演。因此考虑设 $a' = a/d$，$b' = b/d$，原式化为
$$\sum_{i = 1}^{a'}\sum_{j = 1}^{b'}[\gcd(i,j) = 1]$$
然后就可以愉快的反演了。我们知道
$$\mu * 1 = \epsilon$$
所以
$$\epsilon(n) = \sum_{d\mid n}\mu(d)$$
稍微变一下：
$$\epsilon(\gcd(i,j)) = \sum_{d\mid \gcd(i,j)}\mu(d)$$
所以原式化为
$$\sum_{i = 1}^{a'}\sum_{j = 1}^{b'}\sum_{d\mid \gcd(i,j)}\mu(d)$$
考虑写成枚举 $d$ 的形式：
$$\begin{aligned} &\sum_{i = 1}^{a'}\sum_{j = 1}^{b'}\sum_{d\mid \gcd(i,j)}\mu(d)\\ =&\sum_{i = 1}^{a'}\sum_{j = 1}^{b'}\sum_{d = 1}^{\min(a',b')}[d\mid\gcd(i,j)]\mu(d)\\ =&\sum_{d=1}^{\min(a',b')}\mu(d)\sum_{i = 1}^{a'}\sum_{j = 1}^{b'}[d\mid\gcd(i,j)] \end{aligned}$$
考虑到若要使 $d\mid \gcd(i,j)$，$i$ 和 $j$ 必须同为 $d$ 的倍数，根据乘法原理，原式可以化为
$$\sum_{d=1}^{\min(a',b')}\mu(d)\left\lfloor\frac{a'}{d}\right\rfloor\left\lfloor\frac{b'}{d}\right\rfloor$$
预处理出 $\mu$ 的前缀和，再套一个整除分块即可。

#include <cstdio>
#include <cctype>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)

const int maxn = 5e4 + 7;

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int mu[maxn], prime[maxn], tot, vis[maxn];

void getmu()
{
    mu[1] = 1;
    for (int i = 2; i <= maxn - 5; ++i)
    {
        if (!vis[i])
        {
            mu[i] = -1;
            prime[++tot] = i;
        }
        for (int j = 1; j <= tot && i * prime[j] <= maxn - 5; ++j)
        {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
            {
                mu[i * prime[j]] = 0;
                break;
            }
            else
                mu[i * prime[j]] = -mu[i];
        }
    }
    FOR(i, 1, maxn - 5)
        mu[i] += mu[i - 1];
    return;
}

inline int min(int a, int b) {return a < b ? a : b;}

int main()
{
    getmu();
    int T = read();
    while (T--)
    {
        int a = read(), b = read(), d = read();
        a /= d, b /= d;
        int top = min(a, b), ans = 0;
        for (int l = 1, r = 0; l <= top && r <= top; l = r + 1)
        {
            r = min(top, min(a / (a / l), b / (b / l)));
            ans += (a / l) * (b / l) * (mu[r] - mu[l - 1]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

洛谷 P2522 [HAOI2011]Problem b 与此题类似，只不过需要套一个容斥。

例题：洛谷 P2257 YY的GCD

题意：求
$$\sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i,j) \in P]$$
其中 $P$ 为质数集。

思路：

不妨枚举这个质数，如下：
$$\sum_{k\in P}\sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i,j) = k]$$
然后就是像上题一样化简：
$$\begin{aligned} &\sum_{k\in P}\sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i,j) = k]\\ =&\sum_{k\in P}\sum_{i = 1}^{n'}\sum_{j = 1}^{m'}[\gcd(i,j) = 1],\quad n' = \left\lfloor\frac nk \right\rfloor,m' = \left\lfloor\frac mk \right\rfloor\\ =&\sum_{k\in P}\sum_{i = 1}^{n'}\sum_{j = 1}^{m'}\sum_{d\mid \gcd(i,j)}\mu(d)\\ =&\sum_{k\in P}\sum_{d = 1}^{\min(n',m')}\mu(d)\left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor \end{aligned}$$
此时这个式子看上去已经差不多了，但是实际运行的时候还是会 T 掉，考虑设 $T = kd$，有
$$\begin{aligned} &\sum_{k\in P}\sum_{d = 1}^{\min(n',m')}\mu(d)\left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor\\ =&\sum_{k\in P}\sum_{d= 1}^{\min(n',m')}\mu\left(\frac Tk\right)\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\\ \end{aligned}$$
换成枚举 $T$，提前：
$$\begin{aligned} &\sum_{k\in P}\sum_{d= 1}^{\min(n',m')}\mu\left(\frac Tk\right)\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\\ =&\sum_{T = 1}^n\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor\sum_{k\mid T\land k\in P}\mu\left(\frac Tk\right) \end{aligned}$$
$\displaystyle\sum_{k\mid T\land k\in P}\mu\left(\frac Tk\right)$ 是可以预处理的，预处理然后整除分块就可以了。实际实现的时候记得开 long long 并卡卡常（不要处处 long long）

#include <cstdio>
#include <cctype>
#define FOR(i, a, b) for (register int i = a; i <= b; ++i)

const int maxn = 1e7 + 7;

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int min(int a, int b) {return a < b ? a : b;}

typedef long long ll;

int mu[maxn], p[maxn], vis[maxn], tot;
ll sum[maxn];

void getmu()
{
    mu[1] = 1;
    FOR(i, 2, maxn - 5)
    {
        if (!vis[i])
        {
            p[++tot] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= tot && i * p[j] <= maxn - 5; ++j)
        {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0)
            {
                mu[i * p[j]] = 0;
                break;
            }
            mu[i * p[j]] = -mu[i];
        }
    }
    FOR(j, 1, tot)
        for (int i = 1; i * p[j] <= maxn - 5; ++i)
            sum[i * p[j]] += mu[i];
    FOR(i, 1, maxn - 5)
        sum[i] += sum[i - 1];
    return;
}

signed main()
{
    getmu();
    int kase = read();
    while (kase--)
    {
        int n = read(), m = read();
        int top = min(n, m);
        ll ans = 0;
        for (int l = 1, r = 0; l <= top; l = r + 1)
        {
            r = min(top, min(n / (n / l), m / (m / l)));
            ans += (ll)(n / l) * (ll)(m / l) * (sum[r] - sum[l - 1]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

积性函数

定义：
$$\gcd(a, b) = 1 \implies f(a\times b) = f(a)\times f(b)$$
由定义知 $f(1) = 1$

一些魔术：
$$\gcd(a,b) = 1\implies\sum_{d\mid ab}f(d) = \sum_{d_1 \mid a \land d_2\mid b}(f(d_1)\times f(d_2)) = \left(\sum_{d_1\mid a}f(d_1)\right)\times\left(\sum_{d_2\mid b}f(d_2)\right)$$
上面的式子应该比较好理解，利用这个性质我们可以将一个 $n$ 拆分开来求和再乘在一起。通过上式可以推出下式：
$$\begin{aligned} \gcd(a,b) = 1\implies (f*g)(ab) &= \sum_{d\mid ab}\left(f(d)\times g\left(\frac{ab}{d}\right)\right)\\ &=\sum_{d_1\mid a\land d_2\mid b}\left(f(d_1)g\left(\frac{a}{d_1}\right)f(d_2)g\left(\frac{b}{d_2}\right) \right)\\ &=\sum_{d_1\mid a}\left(f(d_1)g\left(\frac{a}{d_1}\right)\right)\times\sum_{d_2\mid b}\left(f(d_2)g\left(\frac{b}{d_2}\right) \right)\\ &= (f*g)(a)\times(f*g)(b) \end{aligned}$$
其中 $f,g$ 为积性函数。

完全积性函数：
$$\forall a,b\in\mathbb N^*,\:f(a\times b) = f(a)\times f(b)$$
例子：$1(n) = 1$，$\mathrm{id}^k(n) = n^k$，$\mathrm{id}(n) = n$

不难发现其具有如下性质
$$f(p^n) = \left(f(p)\right)^n$$
显然。
$$\begin{aligned} (f\times g)*(f\times h) &= \sum_{d\mid n}\left(f(d)\times g(d)\times f\left(\frac n d \right)\times h\left(\frac nd \right) \right)\\ &=f\times\sum_{d\mid n}\left(g(d)\times h\left(\frac nd \right) \right)\\ &=f\times(g*h) \end{aligned}$$

除数函数：
$$\begin{aligned} \tau(n) &= \sum_{d\mid n}1\\ \sigma(n) &= \sum_{d\mid n}d \end{aligned}$$
前面的 $\tau(n)$ 描述了 $n$ 的约数个数，$\sigma(n)$ 则描述的是 $n$ 的约数和。

一般的，
$$\sigma_m(n) = \sum_{d\mid n}d^m = 1 * n^m$$
不难发现，$\tau(n) = \sigma_0(n)$，$\sigma(n) = \sigma_1(n)$，且 $\sigma_m(n)$ 为积性函数，验证如下：

假定 $\gcd(a,b) = 1$
$$\begin{aligned} \sigma_m(a)\times \sigma_m(b) &= (1*a^m)\times(1*b^m)\\ &=\sum_{d_1\mid a}d_1^m\times \sum_{d_2\mid b}d_2^m\\ &=\sum_{d_1\mid a\land d_2\mid b}(d_1d_2)^m\\ &=\sigma_m(ab) \end{aligned}$$
欧拉函数：
$$\phi(n) = \sum_{\substack{1\le k\le n\\\gcd(k, n) = 1}}1$$
更一般地：
$$\phi_m(n) = \sum_{\substack{1\le k_j\le n\\ \gcd(k_1,k_2,\cdots,k_m,n) = 1}}1 = \mu *\mathrm{id}^m$$
其意义为从 $1,2,\cdots,n$ 中选出 $m$ 个不相同且两两互质的数的方案数。

下面证明 $\phi_m = \mu * \mathrm{id}^m$

令 $f(i)$ 为任意完全积性函数
$$\begin{aligned} \sum_{\substack{1\le k_j\le n\\ \gcd(k_1,k_2,\cdots,k_m,n) = 1}}(f_1(k_1)f_2(k_2)\cdots f_m(k_m))&=\sum_{1\le k_j\le n}\left([\gcd(k_1, k_2, \cdots, k_m, n) = 1]\prod_{1\le j\le m}f_j(k_j) \right)\\ &=\sum_{\substack{1\le k_j\le n\\d\mid \gcd(k_1,k_2\cdots,k_m, n)}}\left(\mu(d)\prod_{1\le j\le m}f_j(k_j) \right)\\ &=\sum_{\substack{1\le k_j\le n\\d\mid \gcd(k_1,k_2\cdots,k_m, n)}}\left(\mu(d)\prod_{\substack{1\le j\le m\\k_j'd = k_j}}f_j(k_j'd) \right)\\ &=\sum_{\substack{1\le k_j\le n\\d\mid \gcd(k_1,k_2\cdots,k_m, n)}}\left(\mu(d)\prod_{\substack{1\le j\le m\\k_j'd = k_j}}f_j(d)\prod_{\substack{1\le j\le m\\k_j'd = k_j}}f_j(k_j') \right)\\ \end{aligned}$$
定义 $s_j(i) = \displaystyle\sum_{k = 1}^if_j(k)$，继续化简：
$$\begin{aligned} \sum_{\substack{1\le k_j\le n\\ \gcd(k_1,k_2,\cdots,k_m,n) = 1}}(f_1(k_1)f_2(k_2)\cdots f_m(k_m))&=\sum_{\substack{1\le k_j\le n\\d\mid \gcd(k_1,k_2\cdots,k_m, n)}}\left(\mu(d)\prod_{\substack{1\le j\le m\\k_j'd = k_j}}f_j(d)\prod_{\substack{1\le j\le m\\k_j'd = k_j}}f_j(k_j') \right)\\ &=\sum_{d\mid n}\left(\mu(d)\prod_{1\le j\le m}f_j(d)\prod_{1\le j\le m}s_j\left(\frac nd\right)\right)\\ &=\left(\mu(n)\times\prod_{1\le j\le m}f_j(n)\right) * \prod_{1\le j\le m}s_j(n) \end{aligned}$$
若此时限定 $f_j(n) = 1$，则此时 $\displaystyle \prod_{1\le j\le m}s_j(n) = n^m$
$$\begin{aligned} \sum_{\substack{1\le k_j\le n\\ \gcd(k_1,k_2,\cdots,k_m,n) = 1}}(f_1(k_1)f_2(k_2)\cdots f_m(k_m))&=\sum_{\substack{1\le k_j\le n\\ \gcd(k_1,k_2,\cdots,k_m,n) = 1}}1\\ &=\left(\mu(n)\times\prod_{1\le j\le m}f_j(n)\right) * \prod_{1\le j\le m}s_j(n)\\ &=\mu*\mathrm{id}^m \end{aligned}$$
例：给定 $a_j\:(1\le j\le m)$
ParseError: KaTeX parse error: Undefined control sequence: \ at position 258: …(k_j = k_j'd)\\\̲ ̲=&\sum_{{1\le k…

杜教筛

杜教筛可以求解积性函数的前缀和。

设现在要求积性函数 $f$ 的前缀和，设 $S(n) = \displaystyle\sum_{i=1}^nf(i)$

再随便找一个积性函数 $g$，考虑他们的狄利克雷卷积的前缀和
$$\begin{aligned} &\sum_{i =1}^n(f*g)(i)\\ =&\sum_{i=1}^n\sum_{d\mid i}f(i)g\left(\frac id\right)\\ =&\sum_{i = 1}^n\sum_{j = 1}^{\left\lfloor\frac ni\right\rfloor}g(i)f(j) \\ =&\sum_{i = 1}^n\left(g(i)\sum_{i =1}^{\left\lfloor\frac ni\right\rfloor}f(j)\right)\\ =&\sum_{i=1}^ng(i)S\left(\left\lfloor\frac ni\right\rfloor\right) \end{aligned}$$

现在我们需要求 $S(n)$，所以把它提出来，移项：
$$g(1)S(n) = \sum_{i = 1}^n(f*g)(i) – \sum_{i=2}^ng(i)S\left(\left\lfloor\frac ni\right\rfloor\right)$$
假如我们可以快速求解 $\displaystyle\sum_{i = 1}^n(f*g)(i)$ 并使用数论分块，就可以较快地求得 $g(1)S(n)$

伪代码：

int getsumf(int n)
{
    int ans = fgs(n);// f * g 的前缀和
    for (int l = 2, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        ans -= (g_sum[r] - g_sum[l - 1]) * getsumf(n / l);
    }
    return ans;
}

可见其是一个递归调用的过程。其复杂度为 $O(n^{\frac 34})$，证明如下：

设求出 $S(n)$ 的时间复杂度为 $T(n)$，要求出 $S(n)$ 需要求出 $\sqrt{n}$ 个 $\displaystyle S\left(\left\lfloor\frac ni\right\rfloor\right)$ 的值，故
$$T(n) = \sum_{i = 1}^{\sqrt n}O(\sqrt i) + O\left(\sqrt\frac ni\right) = O\left(n^{\frac34}\right)$$
进一步地，我们可以先筛出前 $m$ 个答案，再使用杜教筛，优化后的复杂度为
$$T(n) = \sum_{i = 1}^{\left\lfloor\frac nm\right\rfloor}\sqrt\frac ni = O\left(\frac{n}{\sqrt m}\right)$$
当 $m = n^\frac23$ 时，$T(n) = n^\frac23$。

例题：洛谷 P4213 【模板】杜教筛（Sum）

题意：求
ParseError: KaTeX parse error: \cr valid only within a tabular/array environment
由狄利克雷卷积我们知道 $\mu*1 = \epsilon$，故 $\epsilon(n) = \displaystyle\sum_{d\mid n}\mu(d)$

所以
$$\begin{aligned} S_1(n)1(1) &= \sum_{i=1}^n\epsilon(i) – \sum_{i=2}^nS_1\left(\left\lfloor\frac ni\right\rfloor\right)\\ S_1(n)&=1-\sum_{i=2}^nS_1\left(\left\lfloor\frac ni\right\rfloor\right) \end{aligned}$$
由之前，我们也知道 $\phi * 1 = \mathrm {id}$

所以
$$\begin{aligned} S_2(n)1(1) &= \sum_{i=1}^n\mathrm{id}(i) – \sum_{i=2}^n1(i)S_2\left(\left\lfloor\frac ni\right\rfloor\right)\\ S_2(n)&=\frac{(n + 1)n}{2} – \sum_{i=2}^nS_2\left(\left\lfloor\frac ni\right\rfloor\right) \end{aligned}$$

#include <cstdio>
#include <cctype>
#include <unordered_map>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)

inline int read()
{
    char c = getchar();
    int s = 0;
    bool x = 0;
    while (!isdigit(c))
        x = x | (c == '-'), c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x?-s:s;
}

typedef unsigned long long ll;

const int maxn = 1e7 + 15;
std::unordered_map<int, ll> Mu, Phi;
ll mu[maxn], phi[maxn];
int vis[maxn], p[maxn], tot;

void init()
{
    mu[1] = 1, phi[1] = 1;
    FOR(i, 2, maxn - 5)
    {
        if (!vis[i])
            p[++tot] = i, mu[i] = -1, phi[i] = i - 1;
        for (int j = 1; j <= tot && i * p[j] <= maxn - 5; ++j)
        {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0)
            {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            mu[i * p[j]] = -mu[i];
            phi[i * p[j]] = phi[i] * (p[j] - 1);
        }
    }
    FOR(i, 2, maxn - 5)
        phi[i] += phi[i - 1], mu[i] += mu[i - 1];
    return;
}

ll getSumPhi(ll n)
{
    if (n <= maxn)
        return phi[n];
    if (Phi[n])
        return Phi[n];
    ll ans = (ll)(n + 1ll) * (ll)n / 2ll;
    for (ll l = 2, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        ans -= (r - l + 1LL) * getSumPhi(n / l);
    }
    return Phi[n] = ans;
}

ll getSumMu(ll n)
{
    if (n <= maxn)
        return mu[n];
    if (Mu[n])
        return Mu[n];
    ll ans = 1;
    for (ll l = 2, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        ans -= (r - l + 1LL) * getSumMu(n / l);
    }
    return Mu[n] = ans;
}

int main()
{
    init();
    int T = read();
    while (T--)
    {
        int n = read();
        printf("%lld %lld\n", getSumPhi(n), getSumMu(n));
    }
    return 0;
}