前言

被各路数学题吊打之后决定苦练推式子能力。

这篇文章打算先整一点莫反的基础知识然后由易到难开始上题和写题解。

大概就是这样。

这里推荐 An_Account — 莫比乌斯反演-让我们从基础开始，其中的例题和本文例题有重复，本文的优势在于例题更多，难度更大以及给出了原题链接。

基本知识

莫比乌斯反演 ( $M\ddot{o}bius\;Inversion$ ) 。

OI中数学题的常考知识点。

墙裂推荐： WeLikeStudying 的博客

莫比乌斯函数

显然写过总结：数论函数总结

狄利克雷卷积

狄利克雷卷积 ( $Dirichlet\;convolution$ )

推荐文章（参考文章）: 算法学习笔记(35): 狄利克雷卷积，文章中给出了一些常用卷积的证明

再放一篇找到的文章留着看：浅析狄利克雷卷积

以及自己之前写的一部分理论知识（已经直接copy过来了数论算法、定理和常用变换

定义：

对于两个数论函数 $f(x),g(x)$ ，定义他们的卷积为

$(f*g)(n) = \sum_{d \mid n} f(d) \cdot g(\frac{n}{d})$

性质：

交换律: $ f \ast g = g \ast f $
结合律: $ ( f \ast g ) \ast h = f \ast ( g \ast h )$
分配律: $ f \ast ( g + h ) = f \ast g + f \ast h $
单位元: $ \varepsilon $ 表示 $[x=1]$ ，满足对任意函数有 $\varepsilon * f = f$
对积性函数: 若 $f$ 为积性， $g$ 为积性，则 $f*g$ 也为积性
对积性函数: 若 $f$ 为积性， $f*g$ 也为积性，则 $g$ 为积性

常用卷积

~~（先放结论，以后慢慢补证明）~~

防止文章头重脚轻，证明放最后。

$f*1 = \sum_{d \mid n} f(d)$ $id_k*1 = \sigma_k$ $\varphi * 1 = id$ $\mu * 1 = \varepsilon$ $id * \mu = \varphi$ $1 * 1 = \tau$

若 $F = 1*f$ 则有：

$f = \mu * F$

基本套路

一、莫比乌斯反演

例如求

$\sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i,j) = 1]$

（P3455 [POI2007]ZAP-Queries几乎就是原题）

过程就是：

$\begin{split} &\;\;\;\;\sum_{i = 1}^n\sum_{j = 1}^m[\gcd(i,j) = 1]\\ &= \sum_{i = 1}^n\sum_{j = 1}^m\varepsilon(\gcd(i,j))\\ &= \sum_{i = 1}^n\sum_{j = 1}^m\sum_{d \mid \gcd(i,j)} \mu(d) \\ &=\sum_{d = 1}^{min(n,m)}\mu(d)\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} 1\\ &= \sum_{d=1}^{\min(n,m)}\mu(d)\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \end{split}$

然后就可以预处理 $\mu$ 整除分块来做了

二、欧拉反演

再比如求：

（原题也有，就是 P2398 GCD SUM）

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

过程就是：

$\begin{split} &\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i,j)\\ =&\sum_{i = 1}^n\sum_{j = 1}^nid(\gcd(i,j))\\ =&\sum_{i = 1}^n\sum_{j = 1}^n\sum_{d \mid \gcd(i,j)} \varphi(d)\\ =& \sum_{d = 1}^n\varphi(d)\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{n}{d} \rfloor} 1\\ =& \sum_{d = 1}^n\varphi(d)\lfloor \frac{n}{d}\rfloor^2 \end{split}$

然后预处理出 $\varphi$ 的前缀和进行一个整除分块即可。

实际上以上两个例题恰好就是莫比乌斯反演的两个基本套路（莫比乌斯反演和欧拉反演）：

莫比乌斯反演：遇到互质就凑成莫比乌斯函数
欧拉反演：遇到 $\gcd$ 就凑成欧拉函数

利用的式子可以在上边的 “常用卷积” 当中轻松找到，这里不再赘述

应用

（为避免拖沓冗长，正常情况下本文题目只给出式子结果，不再放代码）

简单的最大公约数

#6491. 「XXOI 2018」简单的最大公约数
 AT5310 [ABC162E] Sum of gcd of Tuples (Hard)

求 :

$\sum_{i_1 = 1}^m\sum_{i-2 = 1}^m \cdots \sum_{i_n = 1}^m \gcd(i_1,i_2,\cdots,i_n)$

其中 $1 \le n,m \le 10^{11}$,答案对 $2^{64}$ 取模。

属于是对上边套路的基本应用，遇到 $\gcd$ 就凑成欧拉函数所以我们显然有：

$\begin{split} &\sum_{i_1 = 1}^m\sum_{i_2 = 1}^m \cdots \sum_{i_n = 1}^m \gcd(i_1,i_2,\cdots,i_n)\\ =& \sum_{i_1 = 1}^m\sum_{i_2 = 1}^m \cdots \sum_{i_n = 1}^m \sum_{d \mid \gcd(i_1,i_2,\cdots,i_n)} \varphi(d)\\ =& \sum_{d = 1}^m \varphi(d)\sum_{i_1 = 1}^{\lfloor \frac{m}{d} \rfloor}\sum_{i_2 = 1}^{\lfloor \frac{m}{d} \rfloor} \cdots \sum_{i_n = 1}^{\lfloor \frac{m}{d} \rfloor} 1\\ =& \sum_{d = 1}^m \varphi(d)\lfloor \frac{m}{d} \rfloor ^ n \end{split}$

于是发现这个式子可以用整除分块，其中乘 $\varphi(d)$ 的部分看数据范围显然是杜教筛可求，然后就做完了。

对于AtCoder上的那道重题由于数据范围只有 $1e5$ 所以甚至不用写杜教筛（不过写了的话也会快很多）。

式子不难推，最大的难度可能在杜教筛上（

Problem b

P2522 [HAOI2011]Problem b
P3455 [POI2007]ZAP-Queries
P4450 双亲数

求：

$\sum_{x = a}^b \sum_{y = c}^d [\gcd(x,y) = k]$

$n$ 组询问，其中 $1 \le n,k,a,b,c,d \le 5 \times 10^4$ 。

观察问题显然可以直接想到容斥。

设：

$f(n,m) = \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i,j) = k]$

于是原问题转化为：

$f(b,d) - f(a-1,d) - f(b,c-1) + f(a-1,c-1)$

注意这里容斥时 $a,c$ 要减去 $1$

那么可以考虑化简 $f$ ：

以下不妨假设 $n \le m$

$\begin{split} f(n,m) &= \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i,j) = k]\\ &= \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} [ \gcd(i,j) = 1 ]\\ &= \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} \varepsilon(\gcd(i,j))\\ &= \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} \sum_{g \mid \gcd(i,j)} \mu(g) \\ &= \sum_{g=1}^{\frac{n}{k}} \mu(g) \sum_{i=1}^{\lfloor \frac{n}{g\cdot k} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{g\cdot k} \rfloor}1\\ &= \sum_{g = 1}^{\frac{n}{k}}\mu(g) * \lfloor \frac{n}{gk} \rfloor \lfloor \frac{m}{gk} \rfloor \end{split}$

然后就可以使用简单的数论分块求解了（

时间复杂度是 $\Theta(N + T\sqrt{n})$

YY的GCD

P2257 YY的GCD
PGCD - Primes in GCD Table
P2568 GCD

本来没打算写，但是发现难度升的有点快就加上这题缓和下。

求：

$\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j) \in prime]$

首先发现直接求不好求，考虑枚举质数统计贡献。
于是得到（下文使用 $P$ 表示素数集合）：

$\sum_{k \in P} \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i,j) = k]$

后边的部分一看就大有可为：

$\begin{split} &\sum_{k \in P} \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i,j) = k]\\ =&\sum_{k \in P}\sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j) = 1] \\ =&\sum_{k \in P}\sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} \sum_{d \mid \gcd(i,j)} \mu(d) \\ =&\sum_{k \in P} \sum_{d = 1}^{\lfloor \frac{n}{k} \rfloor} \mu(d) \lfloor \frac{n}{kd} \rfloor\lfloor \frac{m}{kd} \rfloor\\ \end{split}$

到这里的复杂度容易发现大概是 $O(T\frac{n\sqrt{n}}{\ln n})$ 级别，即使进行简单的优化也不能通过本题。

于是考虑经典换枚举项：

设 $T = kd$，我们枚举 $T$，得到：

$\sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{k \mid T,k \in P} \mu(\frac{T}{k})$

发现后半部分取值与 $n,m$ 无关。

于是考虑预处理后半部分的前缀和，前半部分每次询问进行整除分块。

后半部分预处理可以直接枚举质数的倍数，仿照埃氏筛的复杂度证明，是 $O(n \log \log n)$ 的，当然还有线性筛和预处理前缀和的 $O(n)$。

对于每次询问只需要进行一次整除分块，这一部分的复杂度是 $O(T \sqrt{n})$。

于是总的复杂度大概是 $O(n \log \log n + T \sqrt{n})$ 或 $\Theta(n + n \log \log n + T \sqrt{n})$。

可以通过本题。

Crash的数字表格

P1829 [国家集训队]Crash的数字表格 / JZPTAB

求：

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

思路比较通畅，所以直接写下去 :

（不妨设 $n \le m$ ）

$\begin{split} \sum_{i = 1}^n \sum_{j = 1}^m \text{lcm}(i,j) &= \sum_{i = 1}^n \sum_{j = 1}^m \frac{i \cdot j}{\gcd(i,j)} \\ &= \sum_{g = 1}^n \sum_{i = 1}^{ \left \lfloor \frac{n}{g} \right \rfloor }\sum_{j = 1}^{ \left \lfloor \frac{m}{g} \right \rfloor } i \cdot j \cdot g [\gcd(i,j) = 1] \\ &= \sum_{g = 1}^n g \sum_{i = 1}^{ \left \lfloor \frac{n}{g} \right \rfloor } i \sum_{j = 1}^{ \left \lfloor \frac{m}{g} \right \rfloor } j \sum_{d \mid \gcd(i,j)} \mu(d) \\ &= \sum_{g = 1}^n g \sum_{d = 1}^{ \left \lfloor \frac{n}{g} \right \rfloor } \mu(d) d^2 \sum_{i = 1}^{ \left \lfloor \frac{n}{gd} \right \rfloor } i \sum_{j = 1}^{ \left \lfloor \frac{m}{gd} \right \rfloor } j \end{split}$

最后两个和式可以用等差数列求和公式 $\Theta(1)$ 求解，前边线性筛 $\mu$ 之后数论分块，

笔者写完了下面的三道例题之后回来写的这题，所以觉得有点水。

但是考虑到上边的例题都是类板子所以给解释下。

感觉这题作为莫反初入门之后的练手题还是不错的，难度并不很大也能体现出一些最基本的想法。

题解里设了很多额外的函数，但我觉得这是不必要甚至多余的。明明像这样本就可以一步到位，但是额外增设函数会使读者心生畏惧，也使自己推式子的条理性有所下降，影响了思维的连贯性。

首先是第一步到第二步枚举，然后把 $\gcd$ 作为枚举项，所以枚举的 $i,j$ 变成 $\gcd$ 的多少倍，有了枚举上界的变化，同时保证是 $\gcd$ 所以要求 $i \bot j$ 。

第二步到第三步同样枚举 $\gcd(i,j)$ ,但要注意由于 $i,j$ 的性质发生变化这里的 $\gcd(i,j)$ 并不在所有条件下都和前文 $g$ 相等，在上一段的基础上这应该是容易理解的。

最后一步同理将枚举项提前，就可以从枚举因数变成枚举倍数，从而去掉求和下标中整除形式的条件。

约数个数和

P3327 [SDOI2015]约数个数和

求：

$\sum_{i = 1}^n \sum_{j = 1}^m \tau(ij)$

其中 $\tau(ij)$ 表示 $i*j$ 的约数个数。

一个重要的公式是：

$\tau(ij) = \sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y) = 1]$

有了这个式子之后这道题就做完一半了。

式子的证明我放在了数论函数总结中 $\tau$ 性质的部分。

考虑有了这个之后我们怎么做：

$\begin{split} &\sum_{i = 1}^n \sum_{j = 1}^m \tau(ij)\\ =& \sum_{i = 1}^n \sum_{j = 1}^m \sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y) = 1]\\ =& \sum_{x = 1}^{n}\sum_{y = 1}^{m} [\gcd(x,y) = 1] \left \lfloor \frac{n}{x} \right \rfloor \left \lfloor \frac{m}{y} \right \rfloor \\ =& \sum_{i = 1}^{n}\sum_{j = 1}^{m} [\gcd(i,j) = 1] \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{j} \right \rfloor \\ \end{split}$

到这里我们终于看到了熟悉的 $\varepsilon(\gcd(i,j))$ ，于是直接进行莫反：

现在流行的写法大概是用莫比乌斯函数直接换 $\gcd$
像这样 :

不妨假设 $n \le m$ :

$\begin{split} &\sum_{i = 1}^{n}\sum_{j = 1}^{m} [\gcd(i,j) = 1] \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{j} \right \rfloor \\ =& \sum_{i = 1}^{n}\sum_{j = 1}^{m}\left( \sum_{g \mid \gcd(i,j)} \mu(g) \right) \left \lfloor \frac{n}{i} \right \rfloor \left \lfloor \frac{m}{j} \right \rfloor \\ =& \sum_{g = 1}^{n} \mu(g) \sum_{i = 1}^{\lfloor \frac{n}{g} \rfloor} \left \lfloor \frac{n}{ig} \right \rfloor \sum_{j = 1}^{\lfloor \frac{m}{g} \rfloor} \left \lfloor \frac{m}{jg} \right \rfloor \end{split}$

在这之后显然上个整除分块就可以结束了。

~~然后显然链接中的式子要比我写在这里的更加清晰，奆佬真是太有耐心啦~~

(原题题解中很多都采用了不流行的写法，而且那种写法并不很好理解)

对于大多数题解中的反演公式中的疑点，奆佬给出了证明。

本文暂不涉及那种设函数的写法，因为它至少在本题可以被以上过程更简明地表出。

简单的数学题

P3768 简单的数学题

求：

$\left ( \sum_{i = 1}^n \sum_{j = 1}^n i \cdot j \cdot \gcd(i,j) \right) \bmod p$

$n \le 10^{10} ,5 \times 10^8 \le p \le 1.1 \times 10^9$ 且 $p$ 为质数。

数据范围要求亚线性解法，所以杜教筛预定（

先写一部分谁都能推出来的式子：

$\begin{split} & \sum_{i = 1}^n \sum_{j = 1}^n i \cdot j \cdot \gcd(i,j)\\ =& \sum_{g = 1}^n\sum_{i = 1}^n\sum_{j = 1}^n i \cdot j \cdot [\gcd(i,j) = g]\\ =& \sum_{g = 1}^n g \sum_{i = 1}^{\left \lfloor \frac{n}{g} \right \rfloor}\sum_{j = 1}^{\left \lfloor \frac{n}{g} \right \rfloor} i \cdot j \cdot g^2[\gcd(i,j) = 1]\\ =& \sum_{g = 1}^n g^3 \sum_{d \mid g} \mu(d)\\ =& \sum_{d = 1}^n \mu(d) \sum_{g = 1}^{\left \lfloor \frac{n}{d} \right \rfloor} g^3 d^2 \sum_{i = 1}^{\left \lfloor \frac{n}{gd} \right \rfloor} i \sum_{j = 1}^{\left \lfloor \frac{n}{gd} \right \rfloor} j \end{split}$

到这里的复杂度显然不能解决问题。

考虑转化，发现后边两项可以 $O(1)$ 求，而且写起来公式需要打很长，所以我们设 $F(x) = \sum_{i = 1}^x i = \frac{x(x+1)}{2}$ ，这样就可以~~少打很多字~~看起来比较直观。

后边的内容不看题解比较难想到。

设 $T = gd$ ，则原式化为：

$\begin{split} & \sum_{d = 1}^n \mu(d) \sum_{g = 1}^{\left \lfloor \frac{n}{d} \right \rfloor} g^3 d^2 \sum_{i = 1}^{\left \lfloor \frac{n}{gd} \right \rfloor} i \sum_{j = 1}^{\left \lfloor \frac{n}{gd} \right \rfloor} j\\ =& \sum_{d = 1}^n \mu(d) \sum_{g = 1}^{\left \lfloor \frac{n}{d} \right \rfloor} g^3 d^2 F^2 \left (\left \lfloor \frac{n}{gd} \right \rfloor \right)\\ =& \sum_{T = 1}^n F^2 \left (\left \lfloor \frac{n}{T} \right \rfloor \right) \sum_{g \mid T} g T^2 \mu \left (\frac{T}{g} \right )\\ =& \sum_{T = 1}^n T^2 F^2 \left (\left \lfloor \frac{n}{T} \right \rfloor \right) \sum_{g \mid T} \mu \left (\frac{T}{g} \right ) id(g) \\ =& \sum_{T = 1}^n F^2 \left (\left \lfloor \frac{n}{T} \right \rfloor \right) T^2 \varphi(T) \\ \end{split}$

到这里仍然有 $O(n)$ 的复杂度，但是发现不能采用最普通的杜教筛处理 $\varphi$ 前缀和的方法来解决，我们需要求解的是 $T^2\varphi(T)$ 的前缀和。

如果我们对于杜教筛的了解不仅限于能过板子的话，这里的问题就变得容易解决了很多。

现在我们有函数 $f(n) = n^2 \varphi(n)$ ，我们需要找到一个函数 $g$ ,使得 $\sum_{i = 1}^n f*g(i)$ 和 $\sum_{i = 1}^n g(i)$ 能够快速求出。

然后发现只要设 $g(n) = n^2$ 就能直接解决问题，这真是太棒了。

具体一点的话就是设了这个 $g$ 之后发现显然 $g$ 的前缀和非常好求，然后考虑 $f * g$ ：

$\begin{split} f * g(n) &= \sum_{d \mid n} f(d) g(\frac{n}{d})\\ &= \sum_{d \mid n} d^2 \varphi(d) \frac{n^2}{d^2}\\ &= n^2\sum_{d \mid n} \varphi(d)\\ &= n^3 \end{split}$

然后bdfs一下得到了公式：

$\sum_{i = 1}^n i^3 = \left ( \frac{n(n+1)}{2} \right )^2$

所以写个整除分块，这道题做完了。

数表

P3312 [SDOI2014]数表

求：

$\sum_{i=1}^n \sum_{j=1}^m \sigma(\gcd(i \cdot j))[\sigma(\gcd(i \cdot j)) \le a]$

~~即将退役的菜鸡在NOIp之前竟然在更新莫反，真是离谱。~~

首先考虑去掉 $ \le a$ 的限制应该怎么做：

$\begin{split} &\sum_{i = 1}^n \sum_{j = 1}^m \sigma(\gcd(i,j))\\ =& \sum_{d=1}^n \sigma(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i,j) = 1] \\ =& \sum_{d=1}^n \sigma(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor} \sum_{g \mid (i,j)} \mu(g) \\ =& \sum_{d=1}^n \sigma(d) \sum_{g = 1}^{\lfloor \frac{n}{d} \rfloor} \mu(g) \lfloor \frac{n}{gd} \rfloor \lfloor \frac{m}{gd} \rfloor\\ \end{split}$

设 $T = gd$ ，于是有：

$\begin{split} &\sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d \mid T} \sigma(d) \mu(\frac{n}{d})\\ =& \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor T \end{split}$

那么在去掉这个限制时我们已经做完了。

虽然最后一步转化对本题不是必须的，但作为去掉限制的部分，这是一个简化。我在题解区没有看到这一步，于是我把它写在这里。

后边要用到的是倒数第二个式子，即

$\sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor \sum_{d \mid T} \sigma(d) \mu(\frac{n}{d})$

考虑 $a$ 的限制在这个式子中实际上是加在 $d$ 的身上，而不同询问之间有很多重复的贡献，我们考虑能否离线询问，然后按照某个顺序排序，使得每次我们只需要在询问前加入多余的贡献，然后进行查询。

事实是可行的，容易发现对于不同的 $a$，上式中只有第二个求和号之后的贡献会发生变化。

于是我们考虑每次更新第二个求和部分的贡献，为了方便维护，这个贡献应该是单调不减的。

具体而言，我们预处理每个数的 $\sigma$ 值，并以此为关键字排序。在每个询问之前把上个询问到这个询问之间多出来的部分的数加入贡献。

考虑怎么统计这个贡献。

题目要求我们对于每个询问的复杂度做到 $O(\sqrt{n})$ 级别，于是我们只能进行一次整除分块。那么在这次整除分块中，我们应当能够 $O(1)$ 地得到第二个和式部分的前缀和。

考虑我们逐个数字加入贡献，而查询的是前缀和，单点修改区间查询，恰好对应了我们熟悉的树状数组。

那么实现的思路明确起来：开一个树状数组记录对于每个 $T$，第二项和式的值，每次单点修改就对于它的所有倍数加上这个点值。

最终做法的复杂度是 $O(n \log^2n + q \sqrt{n} \log n)$，可以通过本题。

那么这道题就做完了。这似乎是我们第一次将莫反和数据结构结合起来。

调代码很痛苦，原因是把值域最大值开成了 $a$ 的最大值（丢人）。

不过调完之后1A了，证明隔壁数论函数那篇里线性处理约数和的部分没有写错。

于神之怒加强版

P4449 于神之怒加强版

求：

$\sum_{i = 1}^n \sum_{j = 1}^m \gcd(i,j)^k$

如果去掉 $k$ 次方的条件，那么我们已经可以随便秒杀这题了。

但是它确实是 $k$ 次方，所以我们不得不动一下脑子了。

首先先按照一点套路枚举 $\gcd$ 推出以下几步：

（也按照套路假设 $n \le m$ ）

$\begin{split} \sum_{i = 1}^n \sum_{j = 1}^m \gcd(i,j)^k &= \sum_{g = 1}^n g^k \sum_{i = 1}^{\left \lfloor \frac{n}{g} \right \rfloor} \sum_{j = 1}^{\left \lfloor \frac{m}{g} \right \rfloor} \left [\gcd(i,j) = 1 \right ] \\ &= \sum_{g = 1}^n g^k \sum_{i = 1}^{\left \lfloor \frac{n}{g} \right \rfloor} \sum_{j = 1}^{\left \lfloor \frac{m}{g} \right \rfloor} \sum_{d \mid \gcd(i,j)} \mu(d) \\ &= \sum_{g = 1}^n g^k \sum_{d = 1}^{\left \lfloor \frac{n}{g} \right \rfloor} \mu(d) \left \lfloor \frac{n}{gd} \right \rfloor\left \lfloor \frac{m}{gd} \right \rfloor \end{split}$

到这里都是相对而言容易得到的，唯一要注意的地方大概就是第二行最后一个求和中 $d \mid (\gcd(i,j))$ 这一部分不要写错，因为提出 $g$ 之后 $\gcd(i,j)$ 的意义发生了变化，它的值也不再一定等于 $g$ 。

之后设 $T = gd$ 并枚举 $T$ ，这是处理这种形式的和式的一种常用手段。

然后就可以得到如下式子：

$\begin{split} &\sum_{T = 1}^n \sum_{g \mid T} g^k \mu \left ( \frac{T}{g} \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_{g \mid T} g^k \mu \left ( \frac{T}{g} \right ) \end{split}$

后边的和式显然就是 $id_k \mu$ ，我们已知 $id_1 \mu = \varphi$ ，但是这个 $k$ 依然使我们感到棘手。

但是我们想到狄利克雷卷积对积性函数的性质：两个积性函数的狄利克雷卷积仍然是积性函数。

我们又想到欧拉筛几乎可以线性筛出所有积性函数。

于是我们只需要筛出 $id_k * \mu$ 就完全解决了这道题。

设 $f(n) = (id_k * \mu)(n) = \sum_{g \mid n} g^k \mu \left ( \frac{n}{g} \right )$

那么对于任何一个数 $n$ ，我们都可以把它唯一分解为质数幂的乘积之后乘起来，这个过程可以隐含在欧拉筛中而不必线性写出。

那么我们的问题就转化为如何求 $f$ 在质数幂处的取值。

对于一个 $n = p^x$ ，其中 $p$ 为质数，我们可以得到：

$f(p^x) = \sum_{d \mid p^x} d^k \mu \left ( \frac{p^x}{d} \right )$

考虑到 $d$ 的取值恰好是 $p$ 的 $1 \sim k$ 次幂，以上和式的被加数只在两种情况下值不为 $0$ :

$d = p^x, \frac{n}{d} = 1$ ,此时值为 $p^{xk}$
$d = p^{x - 1}, \frac{n}{d} = p$ ,此时值为 $-p^{xk - k}$

其余情况的 $\frac{n}{d}$ 都含有平方因子， $\mu$ 值为 $0$

所以我们得到了 $f(p^x) = p^{xk} - p^{xk - k}(x \ge 1)$

然后考虑 $f(p^{x + 1}) = p^{xk + k} - p^{xk}$

结合一下就发现了： $f(p^x) = f(p^{x - 1}) * p^k$ 但是只对 $x > 1$ 成立，因为 $f(1) = 1$ 不满足上边的公式。

然后我们就有了质数幂位置的点值，我们在筛法中把它扩展到全体整数上，由以上过程可以得到这个式子：

$f(i * p) = \begin{cases} f(i) * p^k & i \bmod p = 0\\ f(i) * (p^k - 1) & i \bmod p \neq 0 \end{cases}$

解释一下就是第一种情况是没有增加新的质因子，使用 $f(p^x) = f(p^{x - 1}) * p^k$

第二种情况就是一个新的质因子，使用 $f(p^x) = p^{xk} - p^{xk - k}(x \ge 1)$ 代入 $x = 1$ 得到 $f(p) = p^k - 1$

然后可以进行欧拉筛，我们解决了最后一个问题，这道题做完了。

我们这里第一次解决了被加数是幂形式的问题。

从某篇题解里找来了这个做法的复杂度是 $O(n + tot \times \log k + T \times \sqrt{n})$ 其中 $tot$ 是质数的个数。

数字表格

P3704 [SDOI2017]数字表格

求：

$\prod_{i = 1}^n \prod_{j = 1}^m f_{\gcd(i,j)}$

其中 $f_i$ 表示斐波那契数列的第 $i$ 项。

$f_0 = 0,f_1 = 1$ $f_n = f_{n - 1} + f_{n - 2},n \ge 2$

我们在这里第一次见到连乘形式的问题。

似乎很多对加法运算成立的方法不再适用。不过没关系，我们依然可以枚举 $\gcd$

$\begin{split} \prod_{i = 1}^n \prod_{j = 1}^m f_{\gcd(i,j)} &= \prod_{i = 1}^n \prod_{j = 1}^m \prod_{g = 1}^g f_{g} [\gcd(i,j) = g] \\ &= \prod_{g = 1}^n f_g ^ {\sum_{i = 1}^{\left \lfloor \frac{n}{g} \right \rfloor}\sum_{j = 1}^{\left \lfloor \frac{m}{g} \right \rfloor} [\gcd(i,j) = 1] } \end{split}$

容易发现这个提前 $g$ 的思路是统计每个 $g$ 被从乘了多少次，所以把前边变成和式扔到指数上。

然后发现这个指数我们非常熟悉：

$\begin{split} &\sum_{i = 1}^{\left \lfloor \frac{n}{g} \right \rfloor}\sum_{j = 1}^{\left \lfloor \frac{m}{g} \right \rfloor} [\gcd(i,j) = 1] \\ =& \sum_{d = 1} ^ {\left \lfloor \frac{n}{g} \right \rfloor} \left \lfloor \frac{n}{gd} \right \rfloor \left \lfloor \frac{m}{gd} \right \rfloor \end{split}$

这两步之间的过程都是老套路了，不再赘述。

此时原式变成：

$\prod_{g = 1}^n f_g ^ {\sum_{d = 1} ^ {\left \lfloor \frac{n}{g} \right \rfloor} \left \lfloor \frac{n}{gd} \right \rfloor \left \lfloor \frac{m}{gd} \right \rfloor}$

其实化到这里直接进行整除分块可以通过本题，但是正解还应当继续，于是我们继续。

考虑枚举 $T = gd$ ：

$\prod_{T = 1}^n \prod_{d \mid T} f_d ^{\mu(\frac{T}{d}) \left \lfloor \frac{n}{T} \right \rfloor \left \lfloor \frac{m}{T} \right \rfloor }$

然后因为指数上的乘法等于次方嵌套:

$\prod_{T = 1}^n \prod_{d \mid T} \left ( f_d ^{\mu(\frac{T}{d}) } \right ) ^ { \left \lfloor \frac{n}{T} \right \rfloor \left \lfloor \frac{m}{T} \right \rfloor }$

发现 $\left \lfloor \frac{n}{T} \right \rfloor \left \lfloor \frac{m}{T} \right \rfloor $ 与 $d$ 无关。

根据同指数乘法的运算法则我们得到：

$\prod_{T = 1}^n \left ( \prod_{d \mid T} f_d ^{\mu(\frac{T}{d}) } \right ) ^ { \left \lfloor \frac{n}{T} \right \rfloor \left \lfloor \frac{m}{T} \right \rfloor }$

内层括号内的式子不好再化简，所以直接暴力算，时间大概是 $O(n \log n)$ ，实际上这题有更优的做法，~~但是这里空白太小写不下~~。

补充

对常用卷积的证明

参考内容：算法学习笔记(35): 狄利克雷卷积、浅析狄利克雷卷积

一

$f*1 = \sum_{d \mid n} f(d)$

定义。

二

$id_k*1 = \sigma_k$

证：

$\begin{split} id_k * 1 &= \sum_{d \mid n} id_k(d) \\ &= \sum_{d \mid n} d^k \\ &= \sigma_k \end{split}$

三

$\varphi * 1 = id$

证：

$(\varphi * 1)(n) = \sum_{d \mid n} \varphi(d)$

当 $p$ 为质数时，有：

$\begin{split} \sum_{p^m \mid n} \varphi(p^m) &= \varphi(1) + \sum_{i = 1}^m \varphi(p^i) \\ &= 1 + \sum_{i = 1}^m(p^i - p^{i - 1}) \\ &= p^m \end{split}$

其中第一步到第二步的变化是因为 $p$ 是质数，$p^m$ 的所有因子就是 $p$ 的 $0 \sim m$ 次幂，单独考虑 $0$ 次幂方便后边转化。

第二步到第三步的变化用到了欧拉函数的性质，在数论函数总结中欧拉函数的性质第二条给出了证明。

现在令 $n$ 为正整数，那么它可以被唯一分解为 $\prod p^m$ 。

由于 $\varphi * 1$ 是积性函数，有：

$\begin{split} (\varphi * 1)(n) &= (\varphi * 1)(\prod p^m) \\ &= \prod(\varphi * 1)(p^m) \\ &= \prod p^m\\ &= n \end{split}$

得证。

四

$\mu * 1 = \varepsilon$

证明：

$(\mu * 1)(n) = \sum_{d \mid n} \mu(d)$

当 $n = 1$ 时，结论平凡。

$(\mu * 1)(1) = \mu(1) = 1$

对于 $n \neq 1$，则我们对 $n$ 唯一分解：

$n = \prod_{i = 1}^{k}p_i^{a_i}$

于是 $n$ 的约数 $d$ 可以表达成 $d = \prod_{i = 1}^{b}p_i^{c_i}$ 的形式。

根据莫比乌斯函数的定义式，容易发现只有满足所有 $c_i \le 1$ 的项才有贡献。

对于有 $k$ 个 $c_i = 1$，贡献为 $(-1)^k$

于是 $d$ 的贡献就是：

$\sum_{k = 0}^{b} C_{b}^k (-1)^k$

得到一层组合数偶数项减去奇数项的值，由于每层组合数奇数项等于偶数项，我们得到 $d$ 的贡献为 $0$。

于是 $n$ 的任意约数贡献都为 $0$。

得到 $(\mu * 1)(n) = 0 \space (n \neq 1)$

于是：

$(\mu * 1)(n) = \varepsilon(n) = \begin{cases} 1 & n = 1\\ 0 & n \neq 1 \end{cases}$

得证。

五

$id * \mu = \varphi$

由 $\varphi * 1 = id$ 及式七结论可得。

六

$1 * 1 = \tau$ $(1 * 1)(n) = \sum_{d \mid n} 1$

容易发现取值就是 $n$ 的因子个数。

七