莫比乌斯反演

莫比乌斯反演是组合数学中的一个重要技巧，可以用一个易解问题表达难解问题，从而得到解答.

0. 序

本节用于增加莫比乌斯反演的感性认识，可略读.
如果详读的话，不排除可能有些劝退，那么也是可以跳过的，对学习算法竞赛的莫反套路影响不大.
如果读下来的话，应该会有更全面一些的认识.

莫比乌斯反演是定义在偏序关系计数问题的方法. 要理解偏序，我们先聊全序，比如自然数\({1,2,3,\cdots}\)，\(1<2, 2<3...\)，任意两个不同的自然数都一定有一个小于另一个，那么自然数集合就构成一个全序关系.

偏序，就是任意两个元素，或者在某种意义上一个小/弱/包含于另一个，或者两个不可比，从而形成一个拓扑关系，比如

• 整除关系，\(2|4\) 表示\(2\)能整除\(4\)，而\(3\)就不能整除\(4\)，那么自然数集合能构成一个“关于整除的偏序关系”
• 包含关系，集合\(\{1,2\}\subseteq \{1,2,4\}\)，而\(\{1,3\}\)和\(\{1,2\}\)就不存在谁包含谁，不同集合之间可以构成一个“关于包含的偏序关系”
• 全序关系可以理解为特殊的偏序关系

对于偏序关系，我们可以赋予小于等于号“\(\leq\)”一个更通用的含义来表示各类偏序，即整除关系的“\(|\)”、包含关系的“\(\subseteq\)”，在偏序问题中可以通用地用“\(\leq\)”来表达，那么莫比乌斯反演可以通用的表达为：

对于一个要求解的问题，表达为函数\(f(n)\)，可以定义一个函数\(g(n)=\sum_{d\leq n}f(d)\)，则可以反解出\(f(n)=\sum_{d\leq n}\mu(d)g(d)\).

这里出现了一个函数 \(\mu()\)，称为莫比乌斯函数，不同的偏序关系下有不同的莫比乌斯函数.

解释一下上面的变化过程：

• \(f(n)\)：一个关于\(n\)的计算任务，\(n\)可以是集合，可以是自然数，作为\(f()\)的输入，\(f()\)可以是集合的子集个数、自然数的约数个数这类计数问题.
• \(g(n)=\sum_{d \leq n}f(d)\)：一个“强行定义”的函数，这里不用理解为啥这么定义。固定形式就是\(g(n)\)是所有和\(n\)符合偏序关系的\(d\)代入\(f(d)\)的和. 但是通常\(g(n)\)能从另一个角度“讲个故事”，从而发现按这个故事 用另一种方式很容易计算\(g(n)\) ，这是关键点.
• \(f(n)=\sum_{d\leq n}\mu(d)g(d)\)：对于特定的偏序关系，莫比乌斯函数\(\mu(d)\)的形式是固定的，而\(g(d)\)如果是一个比较好算的东西，那么我们用\(n\)每个符合偏序关系的\(d\)代入\(\mu(d)g(d)\)再求和，就可能较为容易的算出我们要的\(f(n)\)了.

以上就是莫比乌斯反演的典型形式和用途，这里需要一个例子更好去理解，我们就用“集合包含于”这个偏序关系举例吧：

有\(n\)个字母组成的集合\(S\)，\(n\)个小孩，小孩编号的全集为\(X_{n}\)，他们分别有自己不喜欢的字母，比如有\(S=\{a,b,c\}\)共\(3\)个字母，有小孩\(X_{n}=\{1,2,3\}\)，\(1\)号小孩不喜欢\(A_{1}=\{a,c\}\)，\(2\)号小孩不喜欢\(A_{2}=\{c\}\)，\(3\)号小孩不喜欢\(A_{3}=\{a\}\)，那么哪些字母是所有小孩都喜欢的？答案是\(1\)个字母，是\(\{b\}\).

这个问题的数学化描述是

• 设全集为 \(S=\{a,b,\cdots \}\);
• \(n\)个小孩每个小孩不喜欢的字母集合分别为\(A_{1}, A_{2}, \cdots, A_{n}\);
• 其中每个\(A_{i}=\{若干个S中的字母 \}\);
• 求 \(|\bar{A_{1}}\cap \bar{A_{2}} \cap \cdots \cap \bar{A_{n}}|\)，其中 \(\bar{A_{i}}\) 表示\(A_{i}\)的补集，“\(||\)” 表示求集合元素个数.

你可能看出来这是容斥原理模型，但我们先假设这是个比较难算的问题。

定义一个拗口的函数 \(f(K)\)，其中\(K\) 表示\(X_{n}\) 的子集，或者说是\(A_{i}\)的序号——不同的\(i\)组成的集合，比如 \(K=\{1,2\}\)表示\(1\)和\(2\)这两个序号，\(f(K)\) 这个函数求的是“序号不在\(K\)中的那些\(A_{i}\)集合的交集，且去掉所有序号在\(K\)中的那些\(A_{j}\)的元素之后，剩下的元素个数”.

举个例子：\(𝐴_{1} = \{𝑎, 𝑏, 𝑐\}\)， \(𝐴_{2} = \{𝑎, 𝑐\}\)， \(𝐴_{3} = \{𝑐, d, e\}\)， \(𝐴_{4} = \{𝑐, d, e, 𝑓\}\)，\(𝑋_{𝑛} = \{1,2,3,4\}\)，如果\(K=\{1,2\}\)，则序号在\(K\)中的 \(A_{1}, A_{2}\)中出现过的\(\{a, b, c\}\) 都要被排除，序号不在\(K\)中的\(A_{3},A_{4}\)的交集是\(\{c,d,e\}\)，但要排除前面的\(\{a,b,c\}\)，所以\(f(K)\)计数的是\(\{d,e\}\)，也就是 \(f(K)=2\).

\(f(K)\)这个函数是个啥呢？ 把序号全集\(X_{n}\) 代进去，你会发现，\(f(X_{n})\) 就是我们要求的\(|\bar{A_{1}}\cap \bar{A_{2}} \cap \cdots \cap \bar{A_{n}}|\).

\(f(K)\) 是不是一看就好难算的样子？那么我们开始尝试莫比乌斯反演.

按照莫比乌斯反演的流程，我们设

\(g(K)=\sum\limits_{D\subseteq K}f(D)\)

这里不用通用的偏序符号“\(\leq\)”而用集合的“包含于”符号“\(\subseteq\)”以免不习惯，套反演公式得

\(f(K)=\sum\limits_{D\subseteq K}\mu(D,K)g(D)\)

按前面的介绍，\(g(K)\)应该是个容易计算的东西，那我们试着给\(g(K)\)讲个故事：

观察\(g(K)=\sum\limits_{D\subseteq K}f(D)\) ，它是对于\(K\)的所有子集\(D\)，“序号不在\(D\)中的那些\(A_{i\notin D}\)集合的交集，且去掉所有序号在\(D\)中的那些\(A_{j\in D}\)的元素之后，剩下的元素个数，枚举每个\(D\)得到的结果的总和” ，更拗口了！这是个啥呢？

它表示的其实是“序号不在\(K\)中的那些\(A_{i}\)集合的交集元素个数”. 相对\(f(K)\)的区别是不用去掉“序号在\(K\)中的那些\(A_{j}\)”的元素了.

数学表述为 \(g(K)=\sum\limits_{D\subseteq K}f(D)=|\cap_{i\notin K} A_{i} |\). 证明：

可以这样考虑，对于每个元素\(s\)，它在计数时对\(g(K)\)是否有贡献. 对于每个\(s\)，所有包含\(s\)的序号集合\(M\)（\(M=\{i|s\in A_{i}\}\)）， 如果\(X_{n}-M \subseteq K\)，那么\(s\)对\(g(K)\)有贡献. 而\(X_{n}-M \subseteq K \Leftrightarrow X_{n}-K \subseteq M\)，而\(X_{n}-K \subseteq M\) 意味着\(s\)对\(|\cap_{i\notin K} A_{i} |\)有贡献，从而说明，每个对\(g(K)\)有贡献的\(s\)，刚好对应着对\(|\cap_{i\notin K} A_{i} |\)有贡献，即 \(g(K)=|\cap_{i\notin K} A_{i} |\).

“\(|\cap_{i\notin K} A_{i} |\) ” 这个表述可就不拗口了，它就是“序号不在\(K\)中的集合\(A_{i\notin K}\)交集元素个数”，它的计算要简单得多，也即我们找到了一个容易计算的\(g(K)\)，来利用莫比乌斯反演计算\(f(K)\).

这里回顾一下上面的问题及莫比乌斯反演过程：

• 每个小孩有不喜欢的字母，我们要求所有小孩都喜欢的字母；
• 设\(f(K)\) 是“序号不在\(K\)中的那些\(A_{i\notin K}\)的交集且去掉序号在\(K\)中的所有\(A_{j\in K}\)元素的总数；
• 则\(f(X_{n})\)就是所求目标，也即\(|\bar{A_{1}}\cap \bar{A_{2}} \cap \cdots \cap \bar{A_{n}}|\)
• 设\(g(K)=\sum\limits_{D\subseteq K}f(D)\)，而\(g(K)\)是一个容易计算的问题，\(g(K)=|\cap_{i\notin K} A_{i} |\)；
• 莫比乌斯反演得 \(f(K)=\sum\limits_{D\subseteq K}\mu(D,K)g(D)\)

还剩最后一步，\(\mu(D,K)\) 是个啥.

不同的偏序关系下有不同的莫比乌斯函数，这个问题是定义在“包含关系\(\subseteq\)”的偏序集上的，包含关系偏序集的莫比乌斯函数是 \(\mu(A,B)=(-1)^{|B|-|A|}\)，它可以通过数学归纳法证明，这里证明过程略，感兴趣可以查阅组合数学相关资料.

最终呈现整个问题的答案：

\[ \begin{align*} & f(X_{n}) \\ & = |\bar{A_{1}}\cap \bar{A_{2}} \cap \cdots \cap \bar{A_{n}}| \\ & = \sum\limits_{D\subseteq X_{n}}\mu(D,X_{n})g(D) \\ & = \sum\limits_{D\subseteq K}(-1)^{|X_{n}-|D|}|\cap_{i\notin D} A_{i} | \\ & = \sum\limits_{J\subseteq K}(-1)^{J}|\cap_{i\in J} A_{i} | \\ \end{align*} \]

最后一步用\(D\)的补集\(J=X_{n}-D\)做了换元.

到这里就完成了例题的解答，这就是容斥原理公式啊！容斥原理是莫比乌斯反演在有限偏序集上的一个实例.

大家可能会感兴趣其它的偏序关系的莫比乌斯函数是什么样呢？这里不加证明地给出两个：

• 线性有序集，即最直观的\(X_{n}=\{1,2,\cdots,n\}, 1<2<\cdots< n\)

  \(\mu(k,l)=\left \{ \begin{matrix}1 & l=k \\ -1 & l=k+1 \\ 0 & other\end{matrix}\right.\)

• 整除关系，比如\(3\) 能整除 \(6\) 即写作“\(3|6\)”，因为\(\mu()\)用在枚举符合偏序关系的对象的时候，从而如果\(a|b\)则\(\mu(a,b)=\mu(1,\frac{b}{a})\)，于是知道任意\(n\)的\(\mu(1,n)\)即可，省略“\(1\)”简写为\(\mu(n)\)

  \(\mu(n)=\left \{ \begin{matrix}1 & n=1 \\ (-1)^k & n是k个互不相同质数之积 \\ 0 & other\end{matrix}\right.\)

这里“n是k个互不相同质数之积”指\(n\)的因数分解对应\(k\)个质数，且每个质数仅出现 1 次，比如 \(6=2*3\)，而如果有任何质因数出现多于一次，比如\(12=2*2*3\)，\(\mu(12)=0\)就是\(other\)的情况.

虽然不同偏序关系的莫比乌斯函数不同，但我们常见的这类问题其实不多，记几个常见的通常就够用了.

1. 若干定义

算法竞赛中莫比乌斯反演题目一般是处理数论问题，考虑整除关系、最大公约数、最小公倍数这些，以下内容都围绕这类问题阐述.

• 数论函数：定义域为正整数集的函数
• 积性函数：对于互质的整数\(a,b\)，有\(f(ab)=f(a)f(b)\)的函数
  • \(\phi(n)\)：欧拉函数，不大于\(n\)的与\(n\)互质的数的个数
  • \(\mu(n)\)：莫比乌斯函数，这里以及下文特指整除关系偏序下的莫比乌斯函数
• 完全积性函数：对\(a,b\)没有互质限制的\(f(ab)=f(a)f(b)\)的函数
  • \(\epsilon(n)=[n=1]\)：单位函数，\(n\)为1时函数值为\(1\)，否则为\(0\)的函数
  • \(id(n)=n\)：恒等函数
  • \(1(n)=1\)：常数函数
• 狄利克雷卷积：\((f*g)(n)=\sum\limits_{d|n}f(d)g(\frac{n}{d})\)，像是“函数之间的乘法”，满足交换律、结合律

下文中的莫比乌斯函数都指整除偏序关系中的莫比乌斯函数，即：

\[ \mu(n)=\left \{ \begin{matrix}1 & n=1 \\ (-1)^k & n是k个互不相同质数之积 \\ 0 & other\end{matrix}\right. \]

且它有这样一个性质：

\[ (\mu * 1)(n)=\sum\limits_{d|n}\mu(d)=\epsilon(n)=[n=1] \]

证明：设\(n=\prod\limits_{i=1}^{k}p_{i}^{c_{i}}\)，\(n'=\prod\limits_{i=1}^{k}p_{i}\)

\(\sum\limits_{d|n}\mu(d)=\sum\limits_{d|n'}\mu(d)=\sum\limits_{i=1}^{k}C_{k}^{i}\cdot(-1)^{i}=(1+(-1))^{k}\)

仅当\(k=0\)时值为1，\(k=0\)对应着\(n=1\).

以上是下文会用到的东西，放在这里以便遇到的时候查询.

2. 数论分块

这个话题出现在这里有点突兀，但莫比乌斯反演题目经常会需要数论分块，所以这里我们也了解一下.

我们会遇到“除法向下取整的求和问题”： \(\sum\limits_{i=1}^{n}\lfloor \frac{n}{i} \rfloor\)

如果\(n\)很大，直接循环累加\(O(n)\)的复杂度是无法接受的. 我们会发现 \(\lfloor \frac{n}{i} \rfloor\) 的值其实是分段的，由一段又一段相等的值组成，我们只要计算出每一段的起止位置，就可以加速整个过程.

int ret = 0;
for(int i = 1, j; i <= n; i = j + 1) {
    j = n / (n / i);
    ret += (n / i) * (j - i + 1);
}

对每一段的起点 \(i\)，对于区间 \([i, \lfloor \frac{n}{\lfloor\frac{n}{i}\rfloor} \rfloor]\)上的所有 \(x\)，\(\lfloor \frac{n}{x} \rfloor\) 都是相等的.

问题提高点难度：\(\sum\limits_{i=1}^{n}\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor, n< m\)

原理类似，虽然\(\lfloor \frac{n}{i} \rfloor\) 和 \(\lfloor \frac{m}{i} \rfloor\) 各自的区间起止点可能不重叠，但我们可以细分每一个它俩都稳定的小段，代码是类似的.

int ret = 0;
for(int i = 1, j; i <= n; i = j + 1) {
    j = std::min(n / (n / i), m / (m / i));
    ret += (n / i) * (m / i) * (j - i + 1);
}

这里要注意，括号不能乱删，存在除法向下取整的问题不能随便修改计算顺序.

再进一步，计算\(\sum\limits_{i=1}^{n}\mu(i)\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor, n< m\)

也没有很麻烦，我们预处理莫比乌斯函数 \(\mu()\)，并处理好它的前缀和，就可以融入到数论分块里了.

int ret = 0;
for(int i = 1, j; i <= n; i = j + 1) {
    j = std::min(n / (n / i), m / (m / i));
    ret += (n / i) * (m / i) * (mup[j] - mup[i - 1]);
}

这里mup[j] 表示莫比乌斯函数前\(j\)项和 \(\sum\limits_{t=1}^{j}\mu(t)\)

3. 莫比乌斯函数线性筛

在开始莫比乌斯反演之旅前，我们再解决一个问题，莫比乌斯函数的计算.

那一句“n是k个互不相同质数之积”，说得轻巧，对每个\(n\)做一遍质因数分解，这复杂度也略高了.

其实\(\mu(n)\) 也可以类似质数、欧拉函数那样筛出来.

大致原理是在筛质数的过程中，对每个新处理的数i，枚举所有已发现的质数prm[j]，如果prm[j]是i的约数，则prm[j]*i的质因数中prm[j]超过1个，其莫比乌斯函数是mu[prm[j]*i]=0，否则prm[j]*i比i多1个质因数，其莫比乌斯函数是mu[prm[j]*i]=-mu[i].

std::vector<int> mu, prm, mup;  // mu为莫比乌斯函数，prm为质数表，mup为莫比乌斯函数前缀和
void MuList(int mxn) {
    mu.resize(mxn + 10); mup.resize(mxn + 10);
    std::fill(mu.begin(), mu.end(), -2);
    mu[1] = mup[1] = 1;
    prm.clear();
    for (int i = 2; i <= mxn; i ++) {
        if (mu[i] == -2) prm.push_back(i), mu[i] = -1;
        for (int j = 0; j < prm.size() && i * prm[j] <= mxn; j ++) {
            if(i % prm[j] == 0) {
                mu[i * prm[j]] = 0;
                break;
            }
            mu[i * prm[j]] = -mu[i];
        }
    }
    for(int i = 2; i <= mxn; i ++) mup[i] = mup[i - 1] + mu[i];
}

4. 整除关系中的莫比乌斯反演

回顾第0节的典型形式：

• 已知\(f(n)\)是一个数论函数
• 设\(g(n)=\sum\limits_{d|n}f(d)\)
• 则\(f(n)=\sum\limits_{d|n}\mu(d)g(\frac{n}{d})\)

不过它还有另一个形式：

• 设\(g(n)=\sum\limits_{n|d}f(d)\)
• 则\(f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})g(d)\)

主要区别在于，前一种形式，和式枚举的是每一个能整除\(n\)的\(d\)（\(d\leq n\)），而后一种形式，和式枚举的是每一个\(n\)能整除的\(d\)（\(n\leq d\)）.

简要证明：\(g*\mu=f*1*\mu = f*\epsilon = f\)

5. 算法竞赛中的莫比乌斯反演套路

先用 例1 感受这类问题的解决推导过程，然后建议对照第 5.6 节典型套路尝试推导例2～例5.

5.1 例1

求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=1], (n< m)\)

设

• \(f(x)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=x]\)
• \(g(x)=\sum\limits_{x|d}f(d)\)
• \(f(x)=\sum\limits_{x|d}\mu(\frac{d}{x})g(d)\)

其中 \(g(x)=\sum\limits_{x|d}f(d)=\sum\limits_{x|d}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=d]\)求的\(gcd(i,j)\)是\(x\)的倍数的所有情况，其实就是 \(\lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{x} \rfloor\).

于是 \(f(x) =\sum\limits_{x|d}\mu(\frac{d}{x})\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor\)

回到题目，我们要求的是\(x=1\)的情况，故

\[ \begin{align*} f(1) & =\sum\limits_{1|d}\mu(\frac{d}{1})\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \\ & = \sum\limits_{d=1}^{n}\mu(d)\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor \end{align*} \]

这里用上一节的数论分块就搞定了.

不过，每次推导都要设置\(f\)和\(g\)两个函数以及进行莫比乌斯反演的流程可能稍觉麻烦，其实利用第 1 节的性质

\((\mu * 1)(n)=\sum\limits_{d|n}\mu(d)=\epsilon(n)=[n=1]\)

很多题目都可以直接等价变换而不需要做一遍反演.

还以这道题为例，求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=1], (n< m)\)，因为

\(\sum\limits_{d|gcd(i,j)}\mu(d)=\epsilon(gcd(i,j))=[gcd(i,j)=1]\)

式子可直接化为

\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|gcd(i,j)}\mu(d)\)

作求和顺序交换，原则是对求和枚举变量的范围“入内求交，出外求并”，这个知识点可另外了解.

\(\sum\limits_{d=1}^{n}\mu(d)\sum\limits_{d|i}^{n}\sum\limits_{d|j}^{m}1=\sum\limits_{d=1}^{n}\mu(d)\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor\)

得到了相同的结果.

5.2 例2

\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=k], (n< m)\)
解：\(\sum\limits_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{k}\rfloor}[gcd(i,j)=1], (n< m)\)，然后同例1.

5.3 例3

\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}ij[gcd(i,j)=k], (n< m)\)
解：\(k^{2}\cdot \sum\limits_{d=1}^{\lfloor \frac{n}{k}\rfloor}\mu(d)\cdot d^2 \cdot\sum\limits_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i \cdot \sum\limits_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j\)，后两个和式是等差数列求和，前面的一样预处理前缀和，整体上数论分块.

5.4 例4

\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j), (n< m)\)
解：\(\sum\limits_{d=1}\limits^{n} d\sum\limits_{t=1}\limits^{\lfloor \frac{n}{d} \rfloor}t^2\mu(t) \sum\limits_{i}\limits^{\lfloor \frac{n}{td} \rfloor }\sum\limits_{j}\limits^{\lfloor \frac{m}{td} \rfloor } ij\)，见 luoguP1829[国家集训队]Crash的数字表格 / JZPTAB

5.5 例5

\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(i\cdot j), (n< m)\)，其中\(d(k)\)表示\(k\)的约数个数
解：\(\sum\limits_{d}^{\min(n,m)}\mu(d)(\sum_{x=1}^{\lfloor \frac{n}{d} \rfloor}\lfloor \frac{n}{xd} \rfloor)(\sum_{y=1}^{\lfloor \frac{m}{d} \rfloor}\lfloor \frac{m}{yd} \rfloor)\)，见luoguP3327[SDOI2015]约数个数和

5.6 典型套路

1. \(LCM(a,b)\)可转为\(\frac{ab}{gcd(a,b)}\).

2. \(\sum \sum gcd(a,b)\) 可转为条件求和 \(\sum\limits_{d} \sum\sum [gcd(a,b)==d]\)

3. 条件求和\(\sum\limits^{n}\sum\limits^{m} [gcd(a,b)==d]\)可通过换元变为\(\sum\limits^{\lfloor \frac{n}{d} \rfloor}\sum\limits^{\lfloor \frac{m}{d} \rfloor} [gcd(a^{'},b^{'})==1]\)

   类似的另一种形式\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[d|gcd(i,j)] \Leftrightarrow \sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor}1\)，即用枚举\(xd,jd\)替代枚举\(i,j\)消除\([d|gcd(i,j)]\).

4. 可转为莫比乌斯函数表示 \([gcd(a,b)==1] \Leftrightarrow \sum\limits_{d|gcd(a,b)}\mu(d)\)

5. 求和顺序交换以消除枚举\(d|gcd(i,j)\) \[ \sum\limits_{i=1}\limits^{n} \sum\limits_{j=1}\limits^{m} ij \sum\limits_{d|gcd(i,j)}\mu(d) \Leftrightarrow \sum\limits_{d=1}\limits^{\min(n,m)}\mu(d) \sum\limits_{d|i}\limits^{n} \sum\limits_{d|j}\limits^{m} ij \]

6. 枚举约数改为枚举全部，观察等价关系： \[ \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum_{x|i}\sum_{y|j} \Leftrightarrow \sum_{x=1}^{n}\sum_{y=1}^{m} \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y}\rfloor \] 由所有\(i,j\)的所有约数和变为枚举所有约数对其倍数的总贡献.

7. \(\sum\limits_{d|i}^{n} i\) 可以换元消除约束条件 \(\sum\limits_{i^{'}}^{\lfloor \frac{n}{d}\rfloor}i^{'}\)

8. 求和提前，式中加“[]”条件： \(\sum\limits_{x|i}\sum\limits_{y|j}\sum\limits_{p|gcd(x,y)}\mu(p)=\sum\limits_{p=1}^{min(i,j)}\sum\limits_{x|i}\sum\limits_{y|j}[p|gcd(x,y)]\mu(p)\)，相当于把内层for循环提到外层，内层则增加了if.

9. \(\sum\sum [gcd(i,j)=p]\) 这类问题适合莫反，设\(f(x)=\sum\sum[gcd(i,j)=x]\)，则\(g(x)=\sum\limits_{x|d}f(d)\)，从而莫反得到\(f(x)=\sum\limits_{x|d}\mu(\lfloor \frac{d}{x} \rfloor)g(d)\)

10. \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{x|d}[gcd(i,j)=d]=\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor\)，即最大公约数为\(x\)的所有倍数的个数.

6. 基础题单

其实就对应着上文的例题

序号	题号	标题	题型	难度评级	题解
1	luogu P3455	[POI2007]ZAP-Queries	整除关系的计数问题	⭐⭐	👍
2	luogu P2522	[HAOI2011]Problem b	整除关系的计数问题	⭐⭐⭐	👍
3	luogu P2257	YY的GCD	整除关系的计数问题	⭐⭐⭐	👍
4	luogu P3327	[SDOI2015]约数个数和	整除关系的计数问题	⭐⭐⭐⭐	👍
5	luogu P1829	[国家集训队]Crash的数字表格 / JZPTAB	整除关系的计数问题	⭐⭐⭐⭐	👍
6	SPOJ LCMSUM	LCM Sum	整除关系的计数问题	⭐⭐⭐⭐	👍

参考资料

1. Richard A. Brualdi著, 冯速等译. 组合数学(原书第5版). 北京: 机械工业出版社, 2012
2. oi-wiki 莫比乌斯反演
3. An_Account 莫比乌斯反演-让我们从基础开始
4. peng-ym 莫比乌斯反演