莫比乌斯反演和杜教筛

发表于 | 分类于

数论分块

  1. $\left \lfloor \frac{n}{i} \right \rfloor$ 只有 $O(\sqrt{n})$ 个值
  2. 区间 $(\left \lfloor \frac{n}{i} \right \rfloor, \left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor} \right \rfloor)$ 内的取值是一样的，右侧是右端点，一整段值相同的左端点可能还能向左扩, $\left \lfloor \frac{n}{i} \right \rfloor$ 的取值范围是$(\left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor + 1} \right \rfloor+1,\left \lfloor \frac{n}{\left \lfloor \frac{n}{i} \right \rfloor} \right \rfloor)$
  3. $\left \lfloor \frac{n}{ab} \right \rfloor = \left \lfloor \frac{\left \lfloor \frac{n}{a} \right \rfloor}{b} \right \rfloor = \left \lfloor \frac{\left \lfloor \frac{n}{b} \right \rfloor}{a} \right \rfloor$
  4. $\sum_{i=1}^{n}\left \lfloor \frac{n}{i} \right \rfloor i = \sum_{i=1}^{n}\frac{\left \lfloor \frac{n}{i} \right \rfloor (\left \lfloor \frac{n}{i} \right \rfloor + 1)}{2}$ ,类似等差数列求和
  5. 向上取整也有上述性质

使用

有了上述性质，有式子 $F(n) = \sum_{i=1}^{n}f(i) \left \lfloor \frac{n}{i}\right \rfloor$ ，如果可以 $O(1)$ 的求出 $f$ 的区间和，就可以 $O(\sqrt{n})$ 的求出 $F(n)$ 。

同理 $F(n) = \sum_{i=1}^{n}f(i) g(\left \lfloor \frac{n}{i}\right \rfloor)$ 求法类似。

相关代码

求 $F(n) = \sum_{i=1}^{n} f(i) \left \lfloor \frac{n}{i} \right \rfloor$ 的代码 : $O( \sqrt{n} )$

1
2
3
4
5
6
7
8
int F(int n){
	int ans = 0;
	for(int l = 1, r = 0; l <= n; l = r + 1) {
    	r = n / (n / l);  // 区间右端
    	ans += f(l, r) * (n / l);
	}
    return ans;
}

类似的，若上限为 $m (m \leqslant n)$ ，求 $r$ 时：$r = \min(m, n/(n/l));$

对于 $F(n) = \sum_{i=1}^{ \min(n, m) } f(i) \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{i} \right \rfloor$ ，只需要在求右端点 $r$ 时改为 \(r = \min(n/ (n/l), m/ (m/l));\) 类似变形还有 $\sum_{i=1}^{n} k \% i= \sum_{i=1}^{n} k - \left \lfloor \frac{k}{i} \right \rfloor i= nk - \sum_{i=1}^{n}\left \lfloor \frac{k}{i} \right \rfloor i$

1
2
3
4
5
6
ll ans = n * k;
for(ll l = 1,r = 0; l <= n; l=r+1) {
    if(k / l != 0) r = min(k / (k / l), n);
    else r = n;    
    ans -= (k / l) * (r - l + 1) * (l + r) / 2;
}

积性函数

定义

有以下几种定义：

  1. 满足$f(ab) = f(a) * f(b)$且$gcd(a, b) == 1$，$f$ 为积性函数
  2. 满足$f(ab) = f(a) * f(b)$且$gcd(a, b)>1$, $f$为完全积性函数
  3. 若积性函数满足$f(p^n) = f^n(p)$, $f$为完全积性函数

性质

  1. 两个积性函数的狄利克雷卷积还是积性函数
  2. 积性函数的逆也是积性函数
  3. 由定义可得：若 $n = p_{1}^{q_{1}} p_{2}^{q_{2}} …p_{k}^{q_{k}}$ 则 $f(n) = f(p_{1}^{q_{1}})…f(p_{k}^{q_{k}})$

应用

根据上述性质三可以对每个 $f(p_{i}^{qi})$ 求值，在 线性筛素数 的过程中可以获得每个质因数的幂。

$\sigma_{k} (n) $ 表示 $n$ 的因子的 $k$ 次方和，$\sigma_{0}(n)$也就表示因子个数

对于常见的$\sigma_{0} $ 和 $\varphi$ 函数，容易求 $\sigma_{0} (p_{i}^{q_{i}}) = q_{i}+1$ , $\varphi (p_{i}^{q_{i}}) = p_{i}^{q_{i}-1}(p_{i}-1) $

推得

$\sigma_{0} (n) = \prod_{i=1}^{k} (q_{i}+1)$

$\varphi (n) = \prod_{i=1}^{k} p_{i}^{q_{i}-1}(p_{i}-1) = \prod_{i=1}^{k} \frac{p_{i}^{q_{i}-1}(p_{i}-1)}{p_{i}}p_{i} = n \prod_{i=1}^{k} (1-\frac{1}{p_{i}})$

$(\varphi*I) (p^k) = \sum_{d p^k}\varphi(d) = \sum_{i=0}^{k}\varphi(p^i) = 1+(p-1)+p(p-1)+p^2(p-1)+…+p^{k-1}(p-1) = p^k $

所以有 $\varphi * I = id$

常见完全积性函数

单位元函数 : $\epsilon(n) = [n=1] $ —— $\epsilon * f = f$

幂函数 : $id_{k}(n) = n^k$

恒等函数 : $I(n) = 1 = id_0(n)$

单位函数 : $id(n) = n = id_1(n)$

常见积性函数

欧拉函数 : $\varphi(n) $ $∑_{d|n}\varphi(d)=n$

莫比乌斯函数 : $\mu(n) $ —— $ \mu*I = \epsilon$
$∑_{d|n}μ(d)=[n=1]$

约数和函数 : $\sigma (n)$ —— $n$ 的所有约数和

约数个数函数 : $T(n) $—— $n$ 的全部约数个数 = $\sigma_{0}(n)$

因数函数 : $\sigma_{k}(n) = \sum_{d n} d^k$——n的所有约数的k次方和

狄利克雷卷积

定义

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

简写为 ：$h = f*g$

性质

  1. $fg = gf$
  2. $fgh = f(gh)$
  3. $f(g+h) = fg + f*h$
  4. 若 $f$ , $g$ 为积性函数，则 $h=f*g$ 也为积性函数
  5. 逆元 : 对每个 $f(1)\neq 0$ 的函数 $ f $，都存在一个函数 $g$ 使得$f*g=\epsilon$

常用狄利克雷卷积

$I * \mu = \epsilon$

$\mu * id = \varphi$

$I * id = \sigma$

$I * I = T = \sigma_0$

$I * \varphi = id$

结论

$n = \sum_{d n} \varphi(d)$
$\sigma(n) = \sum_{d n} T(d) \varphi(\frac{n}{d})$

$A_{i} = \sum_{j=0}^{i} C_{i}^{j}B_{j}$ 反演得$\Rightarrow$ $B_{i} = \sum_{j=0}^{i}(-1)^jC_{i}^{j}*A_{j}$

莫比乌斯反演

概念引入

定 $\mu$ 为 $I$ 的逆，有 $\mu * I = \epsilon$ ，容易推出： \(\mu(p^k) = \left\{\begin{matrix} 1 & k=0 & \\ -1& k=1 & \\ 0 & k>1 \end{matrix}\right.\) 对于 $n=\prod_{i=1}^{k} p_{i}^{q_{i}}$ ，有： \(\mu(n) = \left\{\begin{matrix} (-1)^k & 所有 q_{i} 都为1 & \\ 0 & 其他 & \end{matrix}\right.\) 现有积性函数 $f$ , 定 $g = fI$ , 有 $f = fI* \mu = g* \mu$ 即： \(g(n) = \sum_{d|n} f(d)\)

\[f(n) = \sum_{d|n} g(d) \mu(\frac{n}{d})\]

公式中的 $i$ 和 $j$ 交换也是成立的 \(g(n) = \sum_{n|d} f(d)\)

\[f(n) = \sum_{n|d} g(d) \mu(\frac{d}{n})\]

例题

洛谷P2257

题目

给定 $n, m$ 求 $\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)是素数]$ .

范围：$n,m \leq 1e7$ ，数据组数 $T \leq 1e3$ .

解法

前置知识：$d gcd(a,b) \Leftrightarrow d a,d b$ .

设函数 $f(x) = [x是素数]$ ，找一个函数 $g$ 满足 $f = gI$ ，那么 $g = f\mu$ \(g(x) = \sum_{d|x} [d是素数] \mu(\frac{x}{d}) \\ = \sum_{p|x} \mu(\frac{x}{p})\) 可用以下代码求得 $g(n)$ ，$O(nloglog n)$：

1
2
3
for (int j = 0; j < prime_count; j++)
  for (int p = prime[j], i = 1; i * p <= N; i++)
    g[i * p] += mu[i];
\[\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)是素数] = \sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j))\\ =\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)} g(d)\\ =\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i,d|j} g(d)\\ =\sum_{d=1}^{\min(n, m)}g(d)\sum_{i\leq n,d|i}1\sum_{j \leq n, d|j} 1\\ =\sum_{d=1}^{\min(n, m)}g(d)\sum_{i=1}^{n}[d|i]\sum_{j=1}^{m}[d|j]\\ =\sum_{d=1}^{\min(n, m)}g(d) \left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor\]

$g(d)$ 可以用上述代码预处理出前缀和，后面部分数论分块单次询问时间复杂度 $O(\sqrt{n}+\sqrt{m})$

简单题

题目

$T$ 组询问，每次给定 $n, m$ 求 $\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)$ .

范围：$n,m \leq 1e6$ ，数据组数 $T \leq 1e4$ ，答案对 $998244353$ 取模 .

题解

利用常用的积性函数 $id(n) = n$ ，已知 $id= \varphi * I$ \(\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j) = \sum_{i=1}^{n}\sum_{j=1}^{m}id(gcd(i,j))\\ =\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i, j)} \varphi(d) \\ =\sum_{d=1}^{\min(n,m)}\varphi(d) \sum_{i=1}^{n}[d|i]\sum_{j=1}^{m}[d|j]\\ =\sum_{d=1}^{\min(n, m)}\varphi(d) \left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor\) 和上题类似，预处理出 $\varphi$ 的前缀和，后面部分直接数论分块即可。

又一题

题目

给出数列 $f_1, f_2,…,f_N$ 的值

$T$ 组询问，每次给定 $n, m$ ，求 $\sum_{i=1}^{n} \sum_{j=1}^{m} f_{gcd(i, j)}$

数据范围：$T \leq 1e4$，$n,m \leq N \leq1e6$

题解

和上题类似，要找出一个 $g$ 使 $f = gI$ , 有 $g = f\mu$ , 即 \(g(n) = \sum_{d|n} f(d)\mu(\frac{n}{d}) = \sum_{ij=n}f(i)\mu(j)\) 可以直接用以下代码获得 $g$ 的值, $O(nlogn)$

1
2
3
4
5
6
void get_g(int N, int *f, int *g) {
  for (int i = 1; i <= N; i++) g[i] = 0;
  for (int i = 1; i <= N; i++)
    for (int j = 1; i * j <= N; j++)
      g[i * j] = (g[i * j] + mu[i] * f[j]) % mod;
}

得到 $g$ 后 \(\sum_{i=1}^{n} \sum_{j=1}^{m} f_{gcd(i, j)}=\sum_{i=1}^{n} \sum_{j=1}^{m} \sum_{d|i,d|j}g(d) \\ =\sum_{d=1}^{min(n, m)}g(d) \left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d} \right \rfloor\) 数论分块即可。

杜教筛

引入

许多数论题目都涉及让求数论函数的前缀和 $S(n) = \sum_{i=1}^{n} f(i)$ , 找一个适当的函数，这里用 $g$ 表示 \(\sum_{i=1}^{n} (f*g)(i) = \sum_{i=1}^{n}\sum_{xy=i}f(x)g(y)\\ =\sum_{y=1}^{n}g(y)\sum_{xy \leq n}^{}f(x)\\ =\sum_{y=1}^{n}g(y)S(\left \lfloor \frac{n}{y} \right \rfloor)\) $y=1$ 时单独提出来 : \(g(1)S(n) = \sum_{i=1}^{n} (f*g)(i) - \sum_{y=2}^{n}g(y)S(\left \lfloor \frac{n}{y} \right \rfloor)\) 所以如果找到适当的函数 $g$ 后能够快速的算出 $\sum_{i=1}^{n} (f*g)(i)$ ，就可以用数论分块在 $O(n^{\frac{3}{4}})$ 的时间复杂度内算出 $S(n)$ 的值。

类似的还有让求 $S(n) = \sum_{i=1}^{n}(f \cdot g)(i)$ 的值，且 $g$ 为完全积性函数，此时有 \(\sum_{i=1}^{n} ((f*I)\cdot g)(i) = \sum_{i=1}^{n}g(i)\sum_{d|i}f(d) \\ = \sum_{i=1}^{n}\sum_{d=1}^{\left \lfloor \frac{n}{i} \right \rfloor}f(d)\cdot g(i\cdot d)\\ =\sum_{i=1}^{n}\sum_{d=1}^{\left \lfloor \frac{n}{i} \right \rfloor}f(d)\cdot g(d) \cdot g(i)\\ =\sum_{i=1}^{n}g(i)S(\left \lfloor \frac{n}{i} \right \rfloor)\) 提出 $y=1$ 部分 \(g(1)S(n) = \sum_{i=1}^{n} ((f*I)\cdot g)(i) - \sum_{i=2}^{n}g(i)S(\left \lfloor \frac{n}{i} \right \rfloor)\) 类似的还有让求 $S(n) = \sum_{i=1}^{n}(f * g)(i)$ 的值，此时有 \(\sum_{i=1}^{n}(f*g*I)(i) = \sum_{i=1}^{n}\sum_{d|i}(f*g)(d)\\ = \sum_{i=1}^{n}\sum_{d=1}^{\left \lfloor \frac{n}{i} \right \rfloor}(f*g)(d)\\ = \sum_{i=1}^{n}S(\left \lfloor \frac{n}{i} \right \rfloor)\) 又有 \(\sum_{i=1}^{n}(f*I*g)(i) = \sum_{i=1}^{n}\sum_{xy=i}(f*I)(x) \cdot g(y)\\ = \sum_{y=1}^{n}g(y)\sum_{xy\leq n}(f*I)(x)\) 所以 \(\sum_{i=1}^{n}S(\left \lfloor \frac{n}{i} \right \rfloor) = \sum_{y=1}^{n}g(y)\sum_{xy\leq n}(f*I)(x)\) 即 \(S(n) = \sum_{y=1}^{n}g(y)\sum_{xy\leq n}(f*I)(x) - \sum_{i=2}^{n}S(\left \lfloor \frac{n}{i} \right \rfloor)\) 还有可能会用到的:若 $f$ 为完全积性函数，$g,h$ 是数论函数，则 $(f \cdot g)(f\cdot h) = f\cdot (gh)$ ，证明如下 \((f \cdot g)*(f\cdot h)(n) = \sum_{d|n}f(d)g(d)f(\frac{n}{d})h(\frac{n}{d}) \\ = f(n)\sum_{d|n}g(d)h(\frac{n}{d}) \\ = f\cdot (g*h)\)

综上所述

  • 让求 $S(n) = \sum_{i=1}^{n} f(i)$ ，有
\[g(1)S(n) = \sum_{i=1}^{n} (f*g)(i) - \sum_{i=2}^{n}g(i)S(\left \lfloor \frac{n}{i} \right \rfloor)\]
  • 让求 $S(n) = \sum_{i=1}^{n}(f \cdot g)(i)$ ，且 $g$ 是完全积性函数有
\[g(1)S(n) = \sum_{i=1}^{n} ((f*I)\cdot g)(i) - \sum_{i=2}^{n}g(i)S(\left \lfloor \frac{n}{i} \right \rfloor)\]
  • 让求 $S(n) = \sum_{i=1}^{n}(f * g)(i)$ ，有
\[S(n) = \sum_{i=1}^{n}g(i)\sum_{ij\leq n}(f*I)(j) - \sum_{i=2}^{n}S(\left \lfloor \frac{n}{i} \right \rfloor)\]
  • 若 $f$ 为完全积性函数，$g,h$ 是数论函数，则 $(f \cdot g)(f\cdot h) = f\cdot (gh)$

例题

洛谷P4213 【模板】杜教筛

题目

求 $\sum_{i=1}^{n}\mu(i)$ 和 $\sum_{i=1}^{n}\varphi(i)$ ，$n \leq 2^{31} -1$

题解

因为 $\mu * I = \epsilon$ ，$\sum_{i=1}^{n}\epsilon(i) = 1$, 所以选 $g = I$ ，直接带入上面的式子即可 \(S(n) = 1-\sum_{i=2}^{n}S(\left \lfloor \frac{n}{i} \right \rfloor)\) 因为 $\varphi*I=id$ ，$\sum_{i=1}^{n}id(i) = \frac{n(n+1)}{2}$ , 依然选 $g=I$，带入 \(S(n) = \frac{n(n+1)}{2}-\sum_{i=2}^{n}S(\left \lfloor \frac{n}{i} \right \rfloor)\)

洛谷P3768 简单的数学题

题目

求 $\sum_{i=1}^{n}\sum_{j=1}^{n}(ij \cdot gcd(i, j)) \mod p$ ，$n,m \leq 1e10$ ， $ 5e8 \leq p \leq 1.1e9$ ，且 $p$ 为质数

题解

因为 $id = \varphi * I$ ，所以 \(\sum_{i=1}^{n}\sum_{j=1}^{n}(ij \cdot gcd(i, j))=\sum_{i=1}^{n}\sum_{j=1}^{n}ij\sum_{d|i,d|j}\varphi(d) \\ =\sum_{d=1}^{n}\varphi(d)\sum_{i=1}^{n}i[d|i]\sum_{j=1}^{n}j[d|j] \\ =\sum_{d=1}^{n}\varphi(d)\cdot(d\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}i)^2\\ =\sum_{d=1}^{n}d^2\varphi(d)Sum(\left \lfloor \frac{n}{d} \right \rfloor)^2\) 其中 $Sum(x) = \frac{x(x+1)}{2}$ ，对 $Sum$ 可以考虑数论分块，$d^2\varphi(d)$ 的区间和可以用前缀和算出，如下代码：

1
2
3
4
5
for (int l = 1, r; l <= n && l <= m; l = r + 1) {
  r = n / (n / l);
  LL t = Sum(n / l);
  ans = (ans + (S(r) - S(l - 1)) * t % p * t % p) % p;
}

现在的任务使如何求 $S(n) = \sum_{i=1}^{n}i^2\varphi(i)$

根据上述引入中的推导，有完全积性函数 $g = id^2$ ，直接带入： \(S(n) = \sum_{i=1}^{n} i^3 - \sum_{i=2}^{n}i^2S(\left \lfloor \frac{n}{i} \right \rfloor)\) 剩下的 $i^2,i^3$ 求和直接用公式即可

BZOJ4176 Lucas的数论

题目

给定 $n$ ，求 $\sum_{i=1}^{n}\sum_{j=1}^{n} d(ij)$ ，$d(k)$ 为 $k$ 的约数个数。$n \leq 1e9$

题解

对 $d(ij)$ ，考虑 $d|ij$ ，令 $a=\frac{i}{gcd(i,d)}, b=\frac{d}{gcd(i,d)}$ ,显然 $a$ 与 $b$ 互质，$a|i，b|j$ \(\sum_{d|ij}I = \sum_{a|i,b|j,a\perp b}I=\sum_{a|i,b|j}[a\perp b]\) 有 \(S(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}d(ij)\\ =\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{a|i}\sum_{b|j}[a\perp b]\\ =\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{a|i}\sum_{b|j}\sum_{d|a,d|b}\mu(d)\\ =\sum_{d=1}^{n}\mu(d)(\sum_{d|a}\sum_{a|i,i\leq n}I)(\sum_{d|b}\sum_{b|j,j\leq n}I)\\ =\sum_{d=1}^{n}\mu(d)(\sum_{a=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\left \lfloor \frac{\left \lfloor \frac{n}{d} \right \rfloor}{a} \right \rfloor)^2\) 令 $F(n) = \sum_{i=1}^{n}\left \lfloor \frac{n}{i} \right \rfloor=\sum_{i=1}^{n}\sum_{ij\leq n}I=\sum_{i=1}^{n}d(i)$ 其中 $d(i) = \sum_{ij\leq n}I$ . \(S(n) = \sum_{d=1}^{n}\mu(d)F(\left \lfloor \frac{n}{d} \right \rfloor)^2\)

奇怪的题目

题目

给 $n$ ，求 $\sum_{i=1}^{n}(\mu^2*(id\cdot \mu))(i)$ . $n\leq 1e9$ .

题解

令 $f=\mu^2*(id\cdot \mu)$ ，则 \(id*f=((id\cdot I)*(id\cdot \mu))*\mu^2\\ =id\cdot(I*\mu)*\mu^2\\ =(id\cdot\epsilon)*\mu^2\\ =I*\mu^2\\ =\mu^2\)

\[\sum_{i=1}^{n}(id*f)(i)=\sum_{i=1}^{n}\mu^2(i)\\ =\sum_{i=1}^{n}\sum_{xy=i}f(x)y\\ =\sum_{y=1}^{n}y\sum_{xy\leq i}f(x)\\ =\sum_{y=1}^{n}yS(\left \lfloor \frac{n}{y} \right \rfloor)\]

所以 $S(n) = \sum_{i=1}^{n}\mu^2(i) - \sum_{i=2}^{n}i\cdot S(\left \lfloor \frac{n}{i} \right \rfloor)$

接下来的问题是求 $\sum_{i=1}^{n}\mu^2(i)$ ，$\mu^2(i) = [i不含平方因子]$ ，定义 $s(i)=\max_{d^2 i}d$ ，则 $\mu^2(i) = [s(i)=1]$ .

$d^2|i，d|s(i)$ , 所以： \(\sum_{i=1}^{n}\mu^2(i)=\sum_{i=1}^{n}[s(i)=i]\\ =\sum_{i=1}^{n}\sum_{d^2|i}\mu(d) \\ =\sum_{d=1}^{\left \lfloor \sqrt{n} \right \rfloor}\mu(d)\left \lfloor \frac{n}{d^2} \right \rfloor\)

又一题

题目

求 $\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i, j)$

题解

前置1：$\sum_{i=1}^{n} i[i\perp n] = \frac{n\varphi(n)}{2}$ , $(n>1)$ ，即小于等于 $n$ 且和 $n$ 互质的数的和。$n=1$ 时答案为 $1$ 。

证明1：若 $x$ 和 $n$ 互质, 有 $gcd(n, x)==1$ ，显然 $gcd(n-x, x)==1$ ，于是在小于等于 $n$ 且与 $n$ 互质的数中 $x$ 和 $n-x$ 总是成对出现且和为 $n$ , 又因为和 $n$ 互质的数有 $\varphi(n)$ 个，所以总和为 $\frac{n\varphi(n)}{2}$ 。

前置2：$\sum_{d n}\frac{n}{d}\varphi(\frac{n}{d}) = \sum_{d n}d\cdot \varphi(d)$

令 \(A(n) = \sum_{i=1}^{n} lcm(i, j)\\ = n\sum_{d|n}\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}i[\frac{n}{d}\perp i]\\ = \frac{n}{2}(1+\sum_{d|n}\frac{n}{d}\varphi(\frac{n}{d})) \\ = \frac{n}{2}(1+\sum_{d|n}d\varphi(d))\)

\[S(n) = \sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i, j) \\ = \sum_{i=1}^{n}(\frac{i}{2}(1+\sum_{d|i}d\varphi(d))) \\ = \frac{1}{2}(\sum_{i=1}^{n}i + \sum_{i=1}^{n}i\sum_{d|i}d\varphi(d))\]

接下来的任务就是如何求 $s(n) = \sum_{i=1}^{n}i\sum_{d|i}d\varphi(d) = \sum_{i=1}^{n}f(i)$ \(f = id\cdot ((id\cdot \varphi)*I) = (id^2\cdot \varphi )*id\) 有 \(f*id^2 = (id^2\cdot \varphi)*(id^2\cdot I)*id= id^3*id\) 即 \(\sum_{i=1}^{n}\sum_{xy = i}y^2f(x) \\ = \sum_{y=1}^{n}y^2\sum_{xy\leq n}f(x) \\ = \sum_{i=1}^{n}i^2 s(\left \lfloor \frac{n}{i} \right \rfloor) = \sum_{i=1}^{n}(id^3*id)(i)\) 所以： \(s(n) = \sum_{i=1}^{n} (id^3*id)(i) - \sum_{i=2}^{n}i^2s(\left \lfloor \frac{n}{i} \right \rfloor)\)

参考内容

jiry_2’s Blog : 杜教筛

浅谈一类积性函数的前缀和

任之洲：积性函数求和的几种方法——2016国家集训队论文

铃悬：杜教筛

abclzr：莫比乌斯反演与杜教筛

杜教筛学习笔记

# 使用单$作为行内数学公式分界符