by TheBigYellowDuck
联赛前恶补知识点...
欧拉函数
欧拉函数 \(\varphi(n)\) 表示 \(1\sim n\) 中与 \(n\) 互质的数的个数。欧拉函数是积性函数。
特殊地，\(\varphi(1)=1\)。对于质数 \(p\) 显然有 \(\varphi(p)=p-1\)。
一些常用的结论：
-
设 \(p\) 是质数，则 \(\varphi(p^k)=p^k-p^{k-1}\)。
证明：对于 \(1\sim p^k\) 的正整数，只有 \(p^{k-1}\) 个 \(p\) 的倍数与 \(p^k\) 不互质，从而 \(\varphi(p^k)=p^k-p^{k-1}\)。
-
设 \(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\)，则有
证明：由于 $\varphi(n)$ 为积性函数，故有$$\displaystyle \varphi(n)=\prod_{i=1}^k \varphi(p_i^{\alpha_i})=\prod_{i=1}^k \left(p_i^{\alpha_i}-p_i^{\alpha_i-1}\right)=\prod_{i=1}^k p_i^{\alpha_i}\times\prod_{i=1}^k \left(1-\dfrac{1}{p_i}\right)=n\prod_{i=1}^k \dfrac{p_i-1}{p_i}$$
这个式子同时指出了一种在 $\mathcal{O}(\sqrt{n})$ 的时间复杂度内求出 $\varphi(n)$ 的方法。
- 设 \(n\) 为正整数，则有
证明：注意到对于 $k\leq n$，若 $\gcd(k,n)=d$，则有 $\gcd\left(\dfrac{k}{d},\dfrac{n}{d}\right)=1$。
令 $f(x)$ 表示满足 $\gcd(k,n)=x$ 且 $k\leq n$ 的正整数 $k$ 的个数，则有 $$n=\sum\limits_{i=1}^n f(i)$$
根据上面的观察得知 $f(x)=\varphi\left(\dfrac{n}{x}\right)$，从而 $$\displaystyle n=\sum_{d\mid n} \varphi\left(\dfrac{n}{d}\right)=\sum_{d\mid n}\varphi(d)$$
P2303 [SDOI2012] Longge 的问题
很好的练习欧拉函数性质的题目。
对于 \(k\leq n\)，若 \(\gcd(k,n)=d\)，则有 \(\gcd\left(\dfrac{k}{d},\dfrac{n}{d}\right)=1\)。从而有
\[\sum_{i=1}^n [\gcd(i,n)=d]=\sum_{i=1}^n\left[\gcd\left(\dfrac{i}{d},\dfrac{n}{d}\right)=1\right]=\varphi\left(\dfrac{n}{d}\right) \]对原式进行变形
\[\sum_{i=1}^n\gcd(i,n)=\sum_{d\mid n}d\sum_{i=1}^n [\gcd(i,n)=d]=\sum_{d\mid n}d\times\varphi\left(\dfrac{n}{d}\right) \]枚举约数，计算 \(\varphi\) 的值即可。
时间复杂度 \(\mathcal{O}(d(n)\sqrt{n})\)。
费马小定理 & 欧拉定理
费马小定理指出，若 \(p\) 为质数，且 \(\gcd(a,p)=1\)，则有
\[a^{p-1}\equiv 1\pmod p \]简证：设模 \(p\) 意义下既约剩余系 \(\{1,2,3,\cdots,p-1\}\)。
由于 \(\gcd(a,p)=1\)，故 \(\{a,2a,3a,\cdots,(p-1)a\}\) 同样构成模 \(p\) 的缩系。从而有
\[a\times 2a\times 3a\times\cdots\times (p-1)a\equiv 1\times2\times3\times\cdots\times (p-1)\pmod p \]左右同时消去 \((p-1)!\) 即证。
费马小定理在很多时候用来求模质数的乘法逆元。容易说明 \(a\) 模 \(p\) 意义下的乘法逆元为 \(a^{p-2}\)。
欧拉定理指出，若 \(\gcd(a,m)=1\)，则有
\[a^{\varphi(m)}\equiv 1\pmod m \]证明类似。构造缩系即可。
扩展欧拉定理表述为
\[a^b\equiv\left\{ \begin{aligned} &a^{b\bmod\varphi(m)} &&\gcd(a,m)=1\\ &a^b && \gcd(a,m)\neq 1,b<\varphi(m)\\ &a^{b\bmod\varphi(m)+\varphi(m)} && \gcd(a,m)\neq 1,b\geq\varphi(m) \end{aligned} \right.\pmod m \]这给了我们一个降幂的手段。
P4139 上帝与集合的正确用法
扩展欧拉定理好题。
幂塔是无穷递归下去的，也就是说，我们可以认为每一层的指数都与原数相等。
设幂塔为 \(a\)，根据扩展欧拉定理
\[2^a\equiv 2^{a\bmod \varphi(p)+\varphi(p)}\pmod p \]会发现对于指数，\(a\) 没有变化，而 \(p\) 减小到了 \(\varphi(p)\)。
这是一个递归结构，递归求解直到 \(\varphi(p)=1\) 就可以停止继续向下递归了。
用线性筛预处理 \(\varphi\) 函数。时间复杂度 \(\mathcal{O}(V+T\log p)\)。
线性筛
线性筛可以在 \(\mathcal{O}(n)\) 的复杂度内筛出所有素数。同时还可以筛出一些积性函数的值。
欧拉函数。注意到在线性筛的过程中，每个合数 \(n\) 都会被最小质因子 \(p_1\) 筛掉。设 \(n'=\dfrac{n}{p_1}\)，我们对 \(n'\) 的值进行讨论。
- 若 \(n'\bmod p_1=0\)，说明 \(n'\) 中包含了 \(n\) 的所有质因子，从而有
- 若 \(n'\bmod p_1\neq 0\)，说明 \(\gcd(n,n')=1\)。由于欧拉函数为积性函数，从而有
莫比乌斯函数。根据 \(\mu(n)\) 的定义可得。与欧拉函数类似的方法讨论。
- 若 \(n' \bmod p_1=0\)，说明 \(n\) 含有平方因子，从而 \(\mu(n)=0\)。
- 若 \(n' \bmod p_1 \neq 0\)，说明 \(p_1\) 是 \(n\) 的一个质因子，从而 \(\mu(n)=-\mu(n')\)。
线性筛一般积性函数 \(f\) 要满足可以在 \(\mathcal{O}(1)\) 的复杂度内计算 \(f(p^k)\) 的值。
预处理 \(\mathrm{low}_i\) 表示 \(i\) 的最小质因子 \(p\) 的 \(v_p(i)\) 次幂，对于 \(i\neq p^k\)，可以通过 \(f(n)=f(\mathrm{low}_i)f\left(\dfrac{i}{\mathrm{low}_i}\right)\) 计算。否则可以单独 \(\mathcal{O}(1)\) 计算。
for (int i = 2; i < N; i++) {
if (!vis[i]) pr[++pcnt] = i, f[i] = ..., low[i] = i; // 单独算 f(p)
for (int j = 1; j <= pcnt && i * pr[j] < N; j++) {
vis[i * pr[j]] = 1;
if (i % pr[j] == 0) { // i 与 p 不互质
low[i * pr[j]] = low[i] * pr[j];
if (i == low[i])
f[i * pr[j]] = ...; // i = p ^ k，单独算 f(p ^ {k + 1})
else
f[i * pr[j]] = f[i / low[i]] * f[low[i * pr[j]]];
break;
}
low[i * pr[j]] = pr[j];
f[i * pr[j]] = f[i] * f[pr[j]]; // i 与 p 互质，f(ip) = f(i)f(p)
}
}
裴蜀定理 & 扩展欧几里得算法
设 \(a,b\) 为不全为 \(0\) 的整数，则存在整数 \(x,y\) 满足 \(ax+by=c\) 的充要条件为 \(\gcd(a,b)\mid c\)。
特别地，当 \(\gcd(a,b)=1\)，则存在整数 \(x,y\) 满足 \(ax+by=1\)。
一般情况下，设 \(a_i\) 为不全为 \(0\) 的整数，则存在整数 \(x_i\) 满足 \(a_1x_1+a_2x_2+\cdots+a_nx_n=c\) 的充要条件为 \(\gcd(a_1,a_2,\cdots,a_n)\mid c\)。
扩展欧几里得算法可以求出不定方程 \(ax+by=\gcd(a,b)\) 的一组可行解解 \((x_0,y_0)\)，并且在 \(b\ne 0\) 时，算法保证求出的解 \(|x_0|\leq b\)，\(|y_0|\leq a\)。
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int t = x;
x = y, y = t - (a / b) * y;
return d;
}
P5656 【模板】二元一次不定方程 (exgcd)
这道题可以练习求一些特殊解的方式。
对于不定方程 \(ax+by=\gcd(a, b)\)，利用 exgcd 算法求出的解 \((x_0,y_0)\) 一定满足 \(|x_0|\leq |b|\)，\(|y_0|\leq |a|\)。可以写出方程的通解
\[\left\{ \begin{aligned} &x=x_0+kb\\ &y=y_0-ka \end{aligned} \right. \]针对这个通解形式进行调整即可得到特殊解。
同余方程 & 乘法逆元
形如 \(ax\equiv b\pmod m\) 的方程。将其化为 \(ax+my=b\) 后用 exgcd 求解。
特殊地，若存在 \(x\) 使得 \(ax\equiv 1\pmod m\)，则称 \(x\) 为 \(a\) 模 \(m\) 的逆元，记作 \(x=a^{-1}\)。
一般情况下，求解逆元可以使用 exgcd。当模数为质数时，可以通过费马小定理求逆元。
模质数 \(p\) 意义下求 \([1,n]\) 的逆元可以通过如下方式递推求解
\[x^{-1}\equiv -\left\lfloor\dfrac{p}{x}\right\rfloor (p\bmod x)^{-1}\pmod p \]另外，存在利用前缀积在 \(\mathcal{O}(n+\log p)\) 的复杂度内预处理任意 \(n\) 个数模 \(p\) 逆元的方法。
P2421 [NOI2002] 荒岛野人
形式化来说，我们要求最小的 \(m\)，使得对于 \(1\leq i,j\leq n\) 都不存在非负整数 \(x\leq\min\{l_i,l_j\}\) 使得
\[c_i+p_ix\equiv c_j+p_jx\pmod m \]我们可以直接解这个同余方程，判断最小非负整数解 \(x\) 是否超过了某个野人的寿命。
将同余方程化为不定方程
\[(p_i-p_j)x+my=c_j-c_i \]由于答案有上界，从小到大暴力枚举，用 exgcd 求解即可。
注意要将答案还原成最小非负整数解。如果算出来的特解是负数要特别注意一下。
时间复杂度 \(\mathcal{O}(n^2m\log c_i)\)。
Lucas 定理
Lucas 定理用来计算组合数模质数 \(p\) 的值。通常在 \(p\) 比较小但组合数的范围很大时使用。
\[\displaystyle \binom{n}{m}\equiv\binom{\lfloor n/p\rfloor}{\lfloor m/p\rfloor}\binom{n\bmod p}{m\bmod p}\pmod p \]我们把前一半递归下去，后一半已经归约到 \(p\) 范围内，可以暴力做。
处理单个组合数的时间复杂度为 \(\mathcal{O}(\log_pn)\)。
P4345 [SHOI2015] 超能粒子炮·改
大力推式子。
记
\[f(n,k)=\sum_{i=0}^k\binom{n}{i} \]用 Lucas 定理拆开
\[f(n,k)=\sum_{i=0}^k\binom{\lfloor n/p\rfloor}{\lfloor i/p\rfloor}\binom{n\bmod p}{i\bmod p} \]用数论分块的思想，枚举 \(\lfloor i/p\rfloor\) 的值，第二个组合数每 \(p\) 个为一个周期。可以提取出来。
\[f(n,k)=\left(\sum_{i=0}^{\lfloor k/p\rfloor-1}\binom{\lfloor n/p\rfloor}{i}\right)\left(\sum_{i=0}^{p-1}\binom{n\bmod p}{i\bmod p}\right)+\binom{\lfloor n/p\rfloor}{\lfloor k/p\rfloor}\sum_{i=\lfloor k/p\rfloor\times p}^{k}\binom{n\bmod p}{i\bmod p} \]观察到第一个求和号就是一个子问题，另外两个求和号结构类似。
记
\[S(n,k)=\sum_{i=0}^k\binom{n\bmod p}{i\bmod p} \]则有
\[f(n,k)=f(\lfloor n/p\rfloor,\lfloor k/p\rfloor-1)\times S(n,p-1)+\binom{\lfloor n/p\rfloor}{\lfloor k/p\rfloor}S(n,k) \]组合数用 Lucas 算，子问题递归下去即可。
时间复杂度 \(\mathcal{O}(p^2+T\log_p^2n)\)。
中国剩余定理
中国剩余定理（Chinese Remainder Theorem）用来求解下列形式的模方程。
\[\left\{ \begin{aligned} x\equiv a_1&\pmod {m_1} \\ x\equiv a_2&\pmod {m_2} \\ &\cdots \\ x\equiv a_n&\pmod {m_n} \\ \end{aligned} \right. \]其中模数 \(m_i\) 两两互质。
定义一些变量
\[M=\prod_{i=1}^nm_i \]\[M_i=\dfrac{M}{m_i} \]\[M_iM_i^{-1}\equiv 1\pmod {m_i} \]中国剩余定理直接给出了方程的通解。
\[x\equiv \sum_{i=1}^n a_iM_iM_i^{-1}\pmod M \]对于一些模数不是质数的情况，可以分解质因数，求解模方程后用 CRT 合并答案。
P2480 [SDOI2010] 古代猪文
对于每个 \(n\) 的约数 \(d\) 都有 \(\dbinom{n}{d}\) 种保留文字的方式，从而
\[p=\sum_{d\mid n}\dbinom{n}{d} \]答案就是 \(g^p\bmod 999911659\)。
由于模数为质数，根据欧拉定理，只需计算 \(p\bmod 999911658\)。模数为质数下我们有 Lucas 定理处理组合数，现在这个模数不是质数了，处理组合数会很麻烦。
考虑对模数质因数分解，由于 \(999911658=2\times 3\times4679\times 35617\)，我们只需要处理在模这四个质数意义下的组合数，用中国剩余定理合并答案。
时间复杂度 \(\mathcal{O}(\sqrt{n}p\log p)\)。
扩展中国剩余定理
扩展中国剩余定理用来处理模数不互质的模方程。说是 exCRT，其实和 CRT 关系不太大。
exCRT 的核心思想是合并方程。假设我们当前有两个方程
\[\left\{ \begin{aligned} x\equiv a_1\pmod {m_1}\\ x\equiv a_2\pmod {m_2} \end{aligned} \right. \]可以写成
\[a_1+m_1p=x=a_2+m_2q \]整理得到
\[m_1p-m_2q=a_2-a_1 \]将 \(p,q\) 看作主元，方程有解当且仅当 \(\gcd(m_1,m_2)\mid (a_2-a_1)\)。
可以通过 exgcd 得到一组特解 \((p_0,q_0)\)，将方程合并为
\[x\equiv a_1+m_1p_0\pmod {\operatorname{lcm}(m_1,m_2)} \]重复合并过程即可。
P4774 [NOI2018] 屠龙勇士
攻击每条龙使用的剑是确定的。可以利用 std::multiset 先算出来。
设攻击第 \(i\) 条龙用的剑攻击力为 \(b_i\)。会发现要求的 \(x\) 就是满足下列模方程的最小正整数解
\[\left\{ \begin{aligned} b_1x\equiv a_1&\pmod {p_1} \\ b_2x\equiv a_2&\pmod {p_2} \\ &\cdots \\ b_nx\equiv a_n&\pmod {p_n} \\ \end{aligned} \right. \]但是这里的 \(b_i\) 不一定与模数 \(p_i\) 互质，不能直接求逆元消掉。但是我们仍然希望转化成熟悉的 \(x\equiv a_i'\pmod {p_i'}\) 通过 exCRT 合并得到解。
先将模方程转化为不定方程
\[bx+py=a \]这个方程有解的充要条件为 \(\gcd(b,p)\mid a\)，可以求出一组特解 \((x_0,y_0)\)。这样就有通解
\[x=x_0+k\dfrac{p}{\gcd(b,p)} \space \space\space (k\in \mathbb{Z}) \]化成同余方程就是
\[x\equiv x_0\pmod {\dfrac{p}{\gcd(b,p)}} \]接下来就可以通过 exCRT 解决了。
注意每条龙都至少要砍 \(\left\lceil\dfrac{a_i}{b_i}\right\rceil\) 次，如果最后答案不到需要补足至 \(\max_{i=1}^n\left\lceil\dfrac{a_i}{b_i}\right\rceil\) 以上。
时间复杂度 \(\mathcal{O}((n+m)\log n+n\log\operatorname{lcm}p_i)\)。
阶 & 原根
满足 \(a^n\equiv 1\pmod m\) 的最小正整数 \(n\) 称为 \(a\) 模 \(m\) 的阶，记作 \(\delta_m(a)\)。
阶有一些很好的性质：
-
\(a^0,a^1,\cdots,a^{\delta_m(a)}\) 模 \(m\) 两两不同余。
证明：考虑反证法，设存在正整数 \(i\neq j\) 满足 \(a^i\equiv a^j\pmod m\)，则有 \(a^{|i-j|}\equiv 1\pmod m\)。由于 \(0<|i-j|<\delta_m(a)\)，这与阶的最小性矛盾。
-
若 \(a^n\equiv 1\pmod m\)，则有 \(\delta_m(a)\mid n\)。
证明：不妨设 \(n=q\times\delta_m(a)+r\)，则有 \(a^r\equiv 1\pmod m\)，由阶的最小性有 \(r=0\)。
-
设 \(a,b\) 为整数，\(m\) 为正整数，则 $$\delta_m(ab)=\delta_m(a)\delta_m(b)$$ 的充要条件为 $$\gcd(\delta_m(a),\delta_m(b))=1$$
若存在整数 \(g\) 满足 \(\gcd(g,m)=1\) 且 \(\delta_m(g)=\varphi(m)\)，则称 \(g\) 为模 \(m\) 的原根。
原根有一些性质：
-
原根判定定理：设 \(m\geq 3\) 且存在原根，\(\gcd(g,m)=1\)，则 \(g\) 为模 \(m\) 原根的充要条件为，对于 \(\varphi(m)\) 的每个质因子 \(p\)，都有 $$g^{\varphi(m)/p}\not\equiv 1\pmod m$$
-
原根个数定理：\(m\) 的原根个数为 \(\varphi(\varphi(m))\)。
-
原根存在定理：\(m\) 存在原根当且仅当 \(m=2,4,p^{\alpha}, 2p^{\alpha}\)，其中 \(p\) 为奇素数。
一点比较实用的性质：
-
\(m\) 的最小原根为 \(\mathcal{O}(m^{0.25})\) 级别。这保证了我们暴力找 \(m\) 的最小原根是可以接受的。
-
设 \(g\) 为 \(m\) 的最小原根，则 \(m\) 的所有原根都可以表示为 \(g^x \bmod m\)，其中 \(\gcd(x,\varphi(m))=1\)。
-
当 \(m\) 为质数时，\(g,g^2,\cdots,g^{m-1}\) 模 \(m\) 两两不同余。这一点告诉我们，对于模质数 \(p\) 意义下的任意数 \(a\)，都可以找到 \(i\) 使得 \(a\equiv g^i\pmod m\)。
BSGS 算法
BSGS 算法用来求解形如 \(a^x\equiv b\pmod m\) 的模方程，要求 \(\gcd(a,m)=1\)。
考虑分块打表。令块长为 \(B\)，设 \(x=q\times B-r\)。则有
\[a^{qB-r}\equiv b\pmod m \]由于 \(a,m\) 互质，从而 \(a\) 存在模 \(m\) 的逆元，则有
\[a^{qB}\equiv ba^r\pmod m \]枚举 \(r\)，打表得到 \(ba^r\bmod m\) 的所有取值。再枚举 \(q\)，只需要查表是否有对应的值即可。
不妨限制 \(x<\delta_m(a)\)，从而枚举上界都不会很高。
时间复杂度 \(\mathcal{O}\left(\left(\dfrac{n}{B}+B\right)\log B\right)\)，取块长 \(B=\lceil\sqrt{m}\rceil\) 有最优复杂度 \(\mathcal{O}(\sqrt{m}\log m)\)。
BSGS 也可以用来求解形如 \(x^a\equiv b\pmod m\) 的模方程。这里要求 \(m\) 为质数。
取 \(m\) 的原根 \(g\)，令 \(x=g^{x'}\)，就有 \((g^a)^{x'}\equiv b\pmod m\)。BSGS 求解 \(x'\) 即可。
P3306 [SDOI2013] 随机数生成器
容易写出通项公式
\[x_{n+1}\equiv a^nx_1+b\sum_{i=0}^{n-1}a^i\pmod p \]令 \(x_{n+1}=t\)，等比数列求和得到
\[t\equiv a^nx_1+b\dfrac{1-a^n}{1-a}\pmod p \]由于 \(p\) 为质数，故 \(1-a\) 存在逆元，设为 \(q\)，则有
\[t\equiv a^nx_1+bq(1-a^n)\pmod p \]将 \(a^n\) 挪到一边
\[a^n(x_1-bq)\equiv t-bq\pmod p \]\(x_1-bq\) 的逆元存在，从而
\[a^n\equiv \dfrac{t-bq}{x_1-bq}\pmod p \]BSGS 即可。
时间复杂度 \(\mathcal{O}(\sqrt{p}\log p)\)。
有一车特判，被创烂了。
P4454 [CQOI2018] 破解 D-H 协议
没太懂这个题 \(g\) 是原根的条件有什么用。楞上 BSGS 就对了。
时间复杂度 \(\mathcal{O}(n\sqrt{p})\)。
不太懂为什么被卡常了。需要 std::unordered_map 加上 O2 才能过。
P4884 多少个 1？
由于模数为质数，可以给同余方程两边同时 \(\times9+1\)，变成 \(10^n\equiv k'\pmod m\)。BSGS 即可。
时间复杂度 \(\mathcal{O}(\sqrt{m})\)。
积性函数 & 狄利克雷卷积
设函数 \(f(x)\) 定义域为 \(\mathbb{N}^*\)，且满足 \(f(1)=1\)。
若对于任意 \(x,y\in\mathbb{N}^*\) 且 \(\gcd(x,y)=1\) 都有 \(f(xy)=f(x)f(y)\) 成立，则 \(f(n)\) 为积性函数。
若对于任意 \(x,y\in\mathbb{N}^*\) 都有 \(f(xy)=f(x)f(y)\) 成立，则 \(f(n)\) 为完全积性函数。
常见的积性函数：
- 单位函数 \(\epsilon(n)=[n=1]\)。
- 常数函数 \(1(n)=1\)。
- 恒等函数 \(\mathrm{id}_k(n)=n^k\)。当 \(k=1\) 时简记为 \(\mathrm{id}(n)\)。
- 除数函数 \(\sigma_k(n)=\sum_{d \mid n} d^k\)。\(\sigma_0(n)\) 就是约数个数 \(d(n)\)，\(\sigma_1(n)\) 就是约数和 \(\sigma(n)\)。
- 欧拉函数 \(\varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1]\)。
- 莫比乌斯函数 \(\mu(n)\)。
数论函数 \(f(n),g(n)\) 的狄利克雷卷积定义为
\[(f*g)(n)=\sum_{d \mid n} f(d)g\left(\dfrac{n}{d}\right) \]记作 \(f*g\)。极其重要。
一些常见函数之间的卷积关系：
- \(\epsilon=\mu * 1\)。
- \(d=1*1\)。
- \(\sigma = \mathrm{id}*1\)。
- \(\varphi=\mu * \mathrm{id}\)。
对第四个式子，可以得到
\[\varphi(n)=\sum_{d \mid n}\mu\left(\dfrac{n}{d}\right)d \]把下标换一下，左边可以提出来一个 \(n\)，除到右边去，可得
\[\dfrac{\varphi(n)}{n}=\sum_{d \mid n}\dfrac{\mu(d)}{d} \]莫比乌斯反演
莫比乌斯函数 \(\mu(n)\) 本质是一个容斥系数。定义为
\[\mu(n)=\begin{cases}1& n=1 \\ 0& \exists\ d>1,\ d^2\mid n \\ (-1)^{\omega(n)}&\mathrm{otherwise}\end{cases} \]其中 \(\omega(n)\) 表示本质不同质因子个数。
\(\mu(n)\) 的很多性质都可以通过狄利克雷卷积来理解。
\[\sum_{d \mid n} \mu(d)=[n=1] \]等价于 \(\mu * 1=\epsilon\)。这也是莫反的核心，很多时候都要利用这个式子进行代换。更多时候会以 \(n=\gcd(i,j)\) 的形式出现，要灵敏地反应出来。
对于数论函数 \(f,g\) 有如下关系成立。
\[f(n)=\sum_{d \mid n} g(d) \Longleftrightarrow g(n)=\sum_{d \mid n}\mu\left(\dfrac{n}{d}\right)f(d) \]证明利用卷积。左边等价于 \(f=g*1\)，两边同时卷上 \(\mu\)，则有 \(g=f *\mu\)。
有时候还能反过来用。
\[f(d)=\sum_{d \mid n} g(n) \Longleftrightarrow g(d)=\sum_{d \mid n}\mu\left(\dfrac{n}{d}\right)f(n) \]这个就不是狄利克雷卷积了。但是也能证明是对的。
P2522 [HAOI2011] Problem b
先可以二维差分，转化为下界都为 \(1\) 的问题。于是问题变成
\[\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=k] \]除掉 \(k\)。
\[\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1] \]把 \(\gcd\) 用莫反化简。
\[\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d \mid \gcd(i,j)}\mu(d) \]交换求和号，转为枚举 \(d\)。记上界 \(c=\min\left\{\left\lfloor\dfrac{n}{k}\right\rfloor,\left\lfloor\dfrac{m}{k}\right\rfloor\right\}\)。
\[\sum_{d=1}^{c}\mu(d)\sum_{i=1}^{\lfloor\frac n k\rfloor}[d\mid i]\sum_{j=1}^{\lfloor\frac m k\rfloor}[d\mid j] \]后面这个东西就是区间内有多少个 \(d\) 的倍数，容易计算。
\[\sum_{d=1}^{c}\mu(d)\left\lfloor\dfrac n{kd}\right\rfloor\left\lfloor\dfrac m{kd}\right\rfloor \]整除分块，只需要处理一下 \(\mu(n)\) 的前缀和。
时间复杂度 \(\mathcal{O}(n+T\sqrt{n})\)。
P2257 YY 的 GCD
考虑枚举质数 \(p\)，计数有多少对 \(\gcd(i,j)=p\)。
\[\sum_{p \in \mathbb{P}}\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=p] \]套用上一题的推导过程，令 \(c=\min\left\{\left\lfloor\dfrac{n}{p}\right\rfloor,\left\lfloor\dfrac{m}{p}\right\rfloor\right\}\)。
\[\sum_{p \in \mathbb{P}}\sum_{d=1}^{c}\mu(d)\left\lfloor\dfrac n{pd}\right\rfloor\left\lfloor\dfrac m{pd}\right\rfloor \]分母上的 \(pd\) 与两个变量有关，很麻烦。不妨令其为 \(T\)，交换求和顺序。
\[\sum_{T=1}^{\min(n,m)}\sum_{p \mid T}\mu\left(\dfrac{T}{p}\right)\left\lfloor\dfrac n{T}\right\rfloor\left\lfloor\dfrac m{T}\right\rfloor \]记 \(f(T)=\sum_{p \mid T}\mu\left(\dfrac{T}{p}\right)\)，计算 \(f\) 的前缀和后整除分块即可。可以用类似埃氏筛的方法做。
时间复杂度 \(\mathcal{O}(n\log \log n + T\sqrt{n})\)。
这种设 \(T\) 的手段是莫反的常见套路。遇到两个变元不好处理的时候不妨一试。
P3327 [SDOI2015] 约数个数和
有一个结论：
\[d(ij)=\sum_{a \mid i}\sum_{b \mid j}[\gcd(a,b)=1] \]证明可以考察每个质因子 \(p\)，具体不详细展开。
有了这个东西，就可以用莫反处理。
\[\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n\sum_{a \mid i}\sum_{b \mid j}[\gcd(a,b)=1] \\ =& \sum_{i=1}^n\sum_{j=1}^n\sum_{a \mid i}\sum_{b \mid j} \sum_{d \mid \gcd(a,b)}\mu(d) \\ =& \sum_{a=1}^n \sum_{b=1}^m \sum_{i=1}^{\left\lfloor\frac{n}{a}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{b}\right\rfloor} \sum_{d \mid \gcd(a,b)}\mu(d)\\ =& \sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{a = 1} ^ {n} \sum\limits_{b = 1} ^ {m} [d \mid a][d \mid b]\sum_{i=1}^{\left\lfloor\frac{n}{a}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{b}\right\rfloor}1\\ =&\sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \sum\limits_{a = 1} ^ {\left\lfloor\frac n d\right\rfloor} \sum\limits_{b = 1} ^ {\left\lfloor\frac m d\right\rfloor} \left\lfloor\frac n {ad} \right\rfloor\left\lfloor\frac m {bd}\right\rfloor \\ =&\sum\limits_{d = 1} ^ {\min(n, m)} \mu(d) \left(\sum\limits_{a = 1} ^ {\left\lfloor\frac n d\right\rfloor} \left\lfloor\frac n {ad} \right\rfloor\right) \left(\sum\limits_{b = 1} ^ {\left\lfloor\frac m d\right\rfloor} \left\lfloor\frac m {bd}\right\rfloor \right) \end{aligned} \]用整除分块预处理
\[g(n)=\sum_{i=1}^n \left\lfloor\dfrac{n}{i}\right\rfloor \]那么答案就是
\[\sum_{d=1}^{\min(n,m)}\mu(d)g\left(\left\lfloor\frac n {d} \right\rfloor\right)g\left(\left\lfloor\frac m {d} \right\rfloor\right) \]时间复杂度 \(\mathcal{O}((T+n)\sqrt{n})\)。
P3704 [SDOI2017] 数字表格
一样的套路，只不过换到了指数上。
\[\prod\limits_{i = 1} ^ n \prod\limits_{j = 1} ^ m f_{\gcd(i, j)} = \prod\limits_{d = 1} ^ {\min(n,m)} f_d ^ {\sum_{i = 1} ^ n \sum_{j = 1} ^ m [\gcd(i, j) = d]} \]对于指数上这个形式，我们再熟悉不过了。令 \(c=\min\left\{\left\lfloor\dfrac{n}{k}\right\rfloor,\left\lfloor\dfrac{m}{k}\right\rfloor\right\}\)。
\[\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d]=\sum_{k=1}^{c}\mu(k)\left\lfloor\dfrac n{kd}\right\rfloor\left\lfloor\dfrac m{kd}\right\rfloor \]令 \(T=kd\)，代入回指数形式。
\[\prod_{T=1}^{\min(n,m)}\prod_{d \mid T}f_d^{\mu\left(\frac T d\right)\left\lfloor\frac n{T}\right\rfloor\left\lfloor\frac m{T}\right\rfloor}=\prod_{T=1}^{\min(n,m)}\left(\prod_{d \mid T}f_d^{\mu\left(\frac T d\right)}\right)^{\left\lfloor\frac n{T}\right\rfloor\left\lfloor\frac m{T}\right\rfloor} \]对每个 \(T\) 预处理 \(f\) 的幂即可。为了方便整除分块，还要预处理一些前缀积之类。
时间复杂度 \(\mathcal{O}(n \log p+n \log\log n + T\sqrt{n})\)。
P1447 [NOI2010] 能量采集
观察一下，格子 \((i,j)\) 处的贡献就是 \(2\gcd(i,j)-1\)。那么答案就是
\[2\left(\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)\right)-nm \]用莫反处理。枚举 \(\gcd\) 的值，按照套路代换。
\[\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j) \\ =&\sum_{k=1}^{\min(n,m)}k\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] \\ =&\sum_{k=1}^{\min(n,m)}k\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]\\ =&\sum_{k=1}^{\min(n,m)}k\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=1}^{\min(n,m)}k\sum_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\dfrac n{kd}\right\rfloor\left\lfloor\dfrac m{kd}\right\rfloor \\ \end{aligned} \]令 \(T=kd\)，继续变换。
\[=\sum_{T=1}^{\min(n,m)}\left\lfloor\dfrac n{T}\right\rfloor\left\lfloor\dfrac m{T}\right\rfloor\sum_{d \mid T}d\mu\left(\dfrac{T}{d}\right) \]会发现后面这个是一个 \(\mathrm{id}*\mu=\varphi\) 的卷积形式。
\[=\sum_{T=1}^{\min(n,m)}\left\lfloor\dfrac n{T}\right\rfloor\left\lfloor\dfrac m{T}\right\rfloor\varphi(T) \]预处理 \(\varphi\) 的前缀和，整除分块即可。
时间复杂度 \(\mathcal{O}(n)\)。