2020-2021:teams:i_dont_know_png:nikkukun:mobius_inversion
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:nikkukun:mobius_inversion [2020/05/12 16:49] nikkukun ↷ 页面名由2020-2021:teams:i_dont_know_png:nikkukun:summary_mobius_inversion改为2020-2021:teams:i_dont_know_png:nikkukun:mobius_inversion |
2020-2021:teams:i_dont_know_png:nikkukun:mobius_inversion [2020/05/26 10:20] (当前版本) nikkukun add some links |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ===== 积性函数 ===== | ===== 积性函数 ===== | ||
| - | |||
| - | 来我们写一下这个部分……（虚晃一枪）啊好，没写呢 | ||
| 数论函数是一类定义域在正整数上的函数。若对数论函数 $f$，且 $\forall a, b$ 使得 $(a, b) = 1$，都满足 | 数论函数是一类定义域在正整数上的函数。若对数论函数 $f$，且 $\forall a, b$ 使得 $(a, b) = 1$，都满足 | ||
| 行 44: | 行 42: | ||
| ===== 狄利克雷卷积 ===== | ===== 狄利克雷卷积 ===== | ||
| - | |||
| - | 来我们写一下这个部分……（虚晃一枪）啊好，没写呢 | ||
| 对数论函数 $f, g$，定义它们的狄利克雷卷积 | 对数论函数 $f, g$，定义它们的狄利克雷卷积 | ||
| $$ | $$ | ||
| - | (f \times g)(n) = \sum _{d \mid n} f(n) \cdot g \left(\dfrac nd \right) | + | (f * g)(n) = \sum _{d \mid n} f(n) \cdot g \left(\dfrac nd \right) |
| $$ | $$ | ||
| 行 103: | 行 99: | ||
| * $\sum_{d \mid n} \mu(d) = [n = 1]$ | * $\sum_{d \mid n} \mu(d) = [n = 1]$ | ||
| - | 第一条性质说明 $\mu(n)$ 可以**线性筛**；第二条性质提供了我们一个**当且仅当** $n = 1$ 时计数的函数，因此在遇到对 $\gcd(i, j) = 1$ 的计数问题中通常会用到它。 | + | 第一条性质说明 $\mu(n)$ 可以**[[..:potassium:sieve#欧拉筛|线性筛]]**；第二条性质提供了我们一个**当且仅当** $n = 1$ 时计数的函数，因此在遇到对 $\gcd(i, j) = 1$ 的计数问题中通常会用到它。 |
| 直接给出代码。 | 直接给出代码。 | ||
| 行 141: | 行 137: | ||
| $$ | $$ | ||
| - | g = f \times 1 | + | g = f * 1 |
| \Leftrightarrow | \Leftrightarrow | ||
| - | f = g \times \mu | + | f = g * \mu |
| $$ | $$ | ||
| 行 169: | 行 165: | ||
| 给出一些常用反演： | 给出一些常用反演： | ||
| - | * $\varepsilon = \mu \times 1$ | + | * $\varepsilon = \mu * 1$ |
| - | * $n = \varphi \times 1 \Leftrightarrow \varphi = n \times \mu$ | + | * $n = \varphi * 1 \Leftrightarrow \varphi = n * \mu$ |
| 行 181: | 行 177: | ||
| 对 $n$ 进行唯一分解 $n = \prod_{i = 1}^m p_i^{k_i}$，则 $n$ 代表了一个高维空间的点 $(k_1, k_2, \ldots, k_m)$，且 $n$ 的所有约数 $d$ 代表的点与 $(k_1, k_2, \ldots, k_m)$ 的关系都是一个高维偏序关系。因此若有 $f = g \times 1$，则 $f$ 实际是 $g$ 的一个高维前缀和。类似地，与 $\mu$ 的狄利克雷卷积可以将这个高维前缀和还原，因此 $\mu$ 实际上是与之相对的高维差分。 | 对 $n$ 进行唯一分解 $n = \prod_{i = 1}^m p_i^{k_i}$，则 $n$ 代表了一个高维空间的点 $(k_1, k_2, \ldots, k_m)$，且 $n$ 的所有约数 $d$ 代表的点与 $(k_1, k_2, \ldots, k_m)$ 的关系都是一个高维偏序关系。因此若有 $f = g \times 1$，则 $f$ 实际是 $g$ 的一个高维前缀和。类似地，与 $\mu$ 的狄利克雷卷积可以将这个高维前缀和还原，因此 $\mu$ 实际上是与之相对的高维差分。 | ||
| - | 利用这个性质，在计算类似 $g(n) = (f \times \mu)(n)$ 时可以不需要枚举每个 $n$ 的因数 $d$，而只用枚举其质因数 $p_i$，依次利用差分将每个 $p_i$ 对应的维度降下来，可以略微降低复杂度。 | + | 利用这个性质，在计算类似 $g(n) = (f * \mu)(n)$ 时可以不需要枚举每个 $n$ 的因数 $d$，而只用枚举其质因数 $p_i$，依次利用差分将每个 $p_i$ 对应的维度降下来，可以略微降低复杂度。 |
| 行 213: | 行 209: | ||
| $$ | $$ | ||
| - | 而 $\left\lfloor \dfrac ng\right\rfloor$ 只有不超过 $\sqrt{n}$ 种取值，$\left\lfloor \dfrac ng\right\rfloor$ 和 $\left\lfloor \dfrac mg\right\rfloor$ 只有不超过 $\sqrt{n}+\sqrt{m}$ 种取值，因此可以将 $[1,n]$ 分成 $\sqrt{n}+\sqrt{m}$ 块，每一块的 $\left\lfloor \dfrac ng\right\rfloor$ 和 $\left\lfloor \dfrac mg\right\rfloor$ 取值都不变，则我们预处理 $\mu$ 后可以对一块区间进行 $\mathcal{O}(1)$ 的统计，总时间复杂度为 $\mathcal{O}(\sqrt{n}+\sqrt{m})$。 | + | 而 $\left\lfloor \dfrac ng\right\rfloor$ 只有不超过 $\sqrt{n}$ 种取值，$\left\lfloor \dfrac ng\right\rfloor$ 和 $\left\lfloor \dfrac mg\right\rfloor$ 只有不超过 $\sqrt{n}+\sqrt{m}$ 种取值，因此可以将 $[1,n]$ 分成 $\sqrt{n}+\sqrt{m}$ 块，每一块的 $\left\lfloor \dfrac ng\right\rfloor$ 和 $\left\lfloor \dfrac mg\right\rfloor$ 取值都不变，则我们预处理 $\mu$ 后可以对一块区间进行 $O(1)$ 的统计，总时间复杂度为 $O(\sqrt{n}+\sqrt{m})$。 |
| === 使用函数变换的方法 === | === 使用函数变换的方法 === | ||
| 行 219: | 行 215: | ||
| 令 $f(k)=\sum_{i=1}^n \sum_{j=1}^m [(i,j)=k]$，$g(k)=\sum_{i=1}^n \sum_{j=1}^m [k \mid (i,j)]$，则 $f(k)$ 就是我们要求的答案。很明显 $k \mid (i,j) \Leftrightarrow k \mid i\text{ 且 } k\mid j$，因此$g(k)=\left\lfloor \dfrac nk \right\rfloor \left\lfloor \dfrac mk \right\rfloor$。 | 令 $f(k)=\sum_{i=1}^n \sum_{j=1}^m [(i,j)=k]$，$g(k)=\sum_{i=1}^n \sum_{j=1}^m [k \mid (i,j)]$，则 $f(k)$ 就是我们要求的答案。很明显 $k \mid (i,j) \Leftrightarrow k \mid i\text{ 且 } k\mid j$，因此$g(k)=\left\lfloor \dfrac nk \right\rfloor \left\lfloor \dfrac mk \right\rfloor$。 | ||
| - | 发现 $g(k)=\sum_{d=1}^{\left\lfloor n/k \right\rfloor}f(d \times k)$，因此有： | + | 发现 $g(k)=\sum_{d=1}^{\left\lfloor n/k \right\rfloor}f(d * k)$，因此有： |
| $$ | $$ | ||
| \begin{aligned} | \begin{aligned} | ||
| - | f(k)=&\sum_{d=1}^{\left\lfloor n/k \right\rfloor}g(d \times k)\mu(d) \\ | + | f(k)=&\sum_{d=1}^{\left\lfloor n/k \right\rfloor}g(d * k)\mu(d) \\ |
| =&\sum_{d=1}^{\left\lfloor n/k \right\rfloor}\left\lfloor \dfrac n{dk} \right\rfloor \left\lfloor \dfrac m{dk} \right\rfloor\mu(d) | =&\sum_{d=1}^{\left\lfloor n/k \right\rfloor}\left\lfloor \dfrac n{dk} \right\rfloor \left\lfloor \dfrac m{dk} \right\rfloor\mu(d) | ||
| \end{aligned} | \end{aligned} | ||
| 行 236: | 行 232: | ||
| $$ | $$ | ||
| - | 类似上面可以证明 $n',m'$ 的取值个数，因此求解也是 $\mathcal{O}(\sqrt{n}+\sqrt{m})$ 的。 | + | 类似上面可以证明 $n',m'$ 的取值个数，因此求解也是 $O(\sqrt{n}+\sqrt{m})$ 的。 |
| 好了，那求了一个区间后，怎么寻找下一个区间？假设我们当前区间开头为 $i$，并假设下一个区间为 $j$ ，则： | 好了，那求了一个区间后，怎么寻找下一个区间？假设我们当前区间开头为 $i$，并假设下一个区间为 $j$ ，则： | ||
| 行 261: | 行 257: | ||
| 以下给出一个简单的证明： | 以下给出一个简单的证明： | ||
| - | 上式显然先决定 $x$ 的取值，再决定 $y$ 的取值。对于一个因子 $p$，若 $p^a \mid i,\ p^b \mid j$，且 $p^{a+b} \mid ij$，则 | + | 上式显然先决定 $x$ 的取值，再决定 $y$ 的取值。对于一个质因子 $p$，若 $p^a \mid i,\ p^b \mid j$，且 $p^{a+b} \mid ij$，则由于 $(x, y) = 1$，一定有 $\min(a, b) = 0$，故 |
| - | + | ||
| - | * $p^0 \mid x$，则表示 $y$ 可以任意选 $p^1, \ldots, p^b$ 等因子，分别映射到因数 $d \mid p^{a+1}, d \mid p^{a+2}, \ldots, d \mid p^{a+b}$； | + | |
| - | * $p^1 \mid x, p^2 \mid x, \ldots, p^a \mid x$，则表示 $x$ 可以任意选 $p^1, \ldots, p^a$ 等因子，分别映射到因数 $d \mid p^{1}, d \mid p^{2}, \ldots, d \mid p^{a}$； | + | |
| - | * $p^0 \mid x$ 且 $q^0 \mid y$ 等因子，映射到因数 $d \mid p^0$； | + | |
| - | + | ||
| - | 综上，因子 $p^0, p^1, \ldots, p^{a+b}$ 都能被唯一地表示出来且一一对应（双射），因此等式成立。 | + | |
| - | 然后还有个推广的神奇大结论： | + | * $p^0 \mid x$，则表示 $y$ 可以任意选 $p^1, \ldots, p^b$ 等因子，分别映射到因数 $p^{a+1}, p^{a+2}, \ldots, p^{a+b}$； |
| + | * $p^1 \mid x, p^2 \mid x, \ldots, p^a \mid x$，则表示 $x$ 可以任意选 $p^1, \ldots, p^a$ 等因子，分别映射到因数 $p^{1}, p^{2}, \ldots, p^{a}$； | ||
| + | * $p^0 \mid x$ 且 $q^0 \mid y$ 等因子，映射到因数 $p^0$； | ||
| - | $$\sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} d(x_1 x_2 \cdots x_k) = \sum_{x_1}^{y_1} \sum_{x_2}^{y_2} \cdots \sum_{x_k}^{y_k} \prod_{i=1}^{k} \left\lfloor \dfrac{y_i}{x_i} \right\rfloor \prod_{i < j } [(x_i, x_j)=1]$$ | + | 综上，因子 $p^0, p^1, \ldots, p^{a+b}$ 都能被唯一地表示出来且一一对应（双射），因此等式成立。[[..:potassium:sieve |
| + | #约数之和|这里]] 提供了另一种关于约数个数和的类似形式证明，但是使用了更合理的映射使得式子易于证明。 | ||
| - | 太神奇，[[http://www.cnblogs.com/iwtwiioi/p/4986325.html|证明]] 需要二重数学归纳，略过。 | ||
| ===== 练习 ===== | ===== 练习 ===== | ||
| 行 293: | 行 285: | ||
| ==== SDOI2008 仪仗队 ==== | ==== SDOI2008 仪仗队 ==== | ||
| - | 不被挡住即行列 $(i,j)=1$（从 $0$ 标号），因此答案为 $(\sum_{i=1}^{n - 1} \sum_{i=1}^{n - 1} [(i,j)=1])+2$（$2$ 个是 $(0,1)$、$(1,0)$）。最终化为 $(\sum_{g=1}^n \mu(g) \lfloor n / g\rfloor ^2)+2$，分块求解。 | + | 不被挡住即行列 $(i,j)=1$（从 $0$ 标号），因此答案为 $(\sum_{i=1}^{n - 1} \sum_{j=1}^{n - 1} [(i,j)=1])+2$（$2$ 个是 $(0,1)$、$(1,0)$）。最终化为 $(\sum_{g=1}^n \mu(g) \lfloor n / g\rfloor ^2)+2$，分块求解。 |
| ==== SDOI2015 约数个数和 ==== | ==== SDOI2015 约数个数和 ==== | ||
| 行 319: | 行 311: | ||
| $$ | $$ | ||
| - | 然后就可以预处理 $f(n)=\sum_{i=1}^n \left\lfloor \dfrac ni \right\rfloor$ 的值，每次询问就可以分块解决。之所以要预处理 $f(n)$，是因为在倒数第二步时如果采用直接计算 $\sum_{i=1}^{n'} \sum_{j=1}^{m'} \left\lfloor \dfrac {n'}i \right\rfloor \left\lfloor \dfrac{m'}j \right\rfloor$ 开销是很大的。但如果我们能预处理，就能做到 $\mathcal{O}(1)$ 计算。 | + | 然后就可以预处理 $f(n)=\sum_{i=1}^n \left\lfloor \dfrac ni \right\rfloor$ 的值，每次询问就可以分块解决。之所以要预处理 $f(n)$，是因为在倒数第二步时如果采用直接计算 $\sum_{i=1}^{n'} \sum_{j=1}^{m'} \left\lfloor \dfrac {n'}i \right\rfloor \left\lfloor \dfrac{m'}j \right\rfloor$ 开销是很大的。但如果我们能预处理，就能做到 $O(1)$ 计算。 |
| - | 预处理时间复杂度 $\mathcal{O}(n\sqrt{n})$，单次询问时间复杂度 $\mathcal{O}(\sqrt{n})$。 | + | 预处理时间复杂度 $O(n\sqrt{n})$，单次询问时间复杂度 $O(\sqrt{n})$。 |
| ==== HNMTC2015#5 Lucas的数论 ==== | ==== HNMTC2015#5 Lucas的数论 ==== | ||
| - | 发现是 //SDOI2015 约数个数和// 的单询问加强版本，上面对 $\mu$ 前缀和的 $\mathcal{O}(n)$ 时间复杂度已经不能满足我们了，因此我们需要用杜教筛求出 $\mu(n)$ 前缀和，在 $\mathcal{O}(n ^{2/3})$ 时间内完成计算。 | + | 发现是 //SDOI2015 约数个数和// 的单询问加强版本，上面对 $\mu$ 前缀和的 $O(n)$ 时间复杂度已经不能满足我们了，因此我们需要用杜教筛求出 $\mu(n)$ 前缀和，在 $O(n ^{2/3})$ 时间内完成计算。 |
| 行 332: | 行 324: | ||
| 比较有意思的莫比乌斯反演题。 | 比较有意思的莫比乌斯反演题。 | ||
| - | 枚举比值 $k=\dfrac {p}{q}\ge 1$ 中的 $p,q$，再枚举最短边 $x$，$x+kx>k^2x$ 可以得到约束 $k<\Phi=\dfrac{1+\sqrt 5}{2}$ ，即 $q\le p<\Phi q$ 。同时 $x$ 需要为 $q^2$ 的整数倍，故 $q\le \sqrt n$ ，设 $x=iq^2$ ，式子化为： | + | 枚举比值 $k=\dfrac {p}{q}\ge 1$ 中的 $p,q$，再枚举最短边 $x$，$x+kx>k^2x$ 可以得到约束 $k<\phi=\dfrac{1+\sqrt 5}{2}$ ，即 $q\le p<\phi q$ 。同时 $x$ 需要为 $q^2$ 的整数倍，故 $q\le \sqrt n$ ，设 $x=iq^2$ ，式子化为： |
| $$ | $$ | ||
| \begin{aligned} | \begin{aligned} | ||
| - | &\sum_{q=1}^{\sqrt n}\sum_{p=q}^{\Phi q}[(p,q)=1]\sum_{i=1}^{+\infty}[ip^2\le n]\\ | + | &\sum_{q=1}^{\sqrt n}\sum_{p=q}^{\phi q}[(p,q)=1]\sum_{i=1}^{+\infty}[ip^2\le n]\\ |
| - | =&\sum_{q=1}^{\sqrt n}\sum_{p=q}^{\Phi q}[(p,q)=1]\left\lfloor\dfrac{n}{p^2}\right\rfloor | + | =&\sum_{q=1}^{\sqrt n}\sum_{p=q}^{\phi q}[(p,q)=1]\left\lfloor\dfrac{n}{p^2}\right\rfloor |
| \end{aligned} | \end{aligned} | ||
| $$ | $$ | ||
| 行 344: | 行 336: | ||
| 发现可以将 $p$ 前提，故找出 $p$ 的范围。由于 $xk^2=ip^2\le n$，$p\le \sqrt n$ 。原式进一步化为： | 发现可以将 $p$ 前提，故找出 $p$ 的范围。由于 $xk^2=ip^2\le n$，$p\le \sqrt n$ 。原式进一步化为： | ||
| - | $$=\sum_{p=1}^{\sqrt n}\left\lfloor\dfrac{n}{p^2}\right\rfloor\sum_{q=\lceil p / \Phi \rceil}^{p}[(p,q)=1]$$ | + | $$=\sum_{p=1}^{\sqrt n}\left\lfloor\dfrac{n}{p^2}\right\rfloor\sum_{q=\lceil p / \phi \rceil}^{p}[(p,q)=1]$$ |
| - | 此时考虑简化对 $q$ 求和部分。我们发现这部分就是 $\varphi(p)-\sum_{i=1}^{\lceil p / \Phi \rceil -1}[(i,p)=1]$ ，而 $\sum_{i=1}^{n}[(i,p)=1]$ 很容易反演为 $\sum_{d\mid p}\mu(d)\lfloor\dfrac nd\rfloor$ 。枚举 $p$ 以及 $p$ 的每个因数 $d$ ，由于 $1\sim n$ 约数个数和是 $\mathcal{O}(n\log n)$ 的，故复杂度为 $\mathcal{O}(\sqrt n \log n)$ 。 | + | 此时考虑简化对 $q$ 求和部分。我们发现这部分就是 $\varphi(p)-\sum_{i=1}^{\lceil p / \phi \rceil -1}[(i,p)=1]$ ，而 $\sum_{i=1}^{n}[(i,p)=1]$ 很容易反演为 $\sum_{d\mid p}\mu(d)\lfloor\dfrac nd\rfloor$ 。枚举 $p$ 以及 $p$ 的每个因数 $d$ ，由于 $1\sim n$ 约数个数和是 $O(n\log n)$ 的，故复杂度为 $O(\sqrt n \log n)$ 。 |
| - | [[https://loj.ac/article/1679|这里]] 提供了一个 $\mathcal{O}(\sqrt n\log \log \sqrt n)$ 的做法，该做法基于莫比乌斯反演的前缀和和差分意义，使得计算 $g(n) = (f \times \mu)(n)$ 时不需要枚举每个 $n$ 的因数 $d$，而只用枚举质因数 $p_i$ 使复杂度略微下降。 | + | [[https://loj.ac/article/1679|这里]] 提供了一个 $O(\sqrt n\log \log \sqrt n)$ 的做法，该做法基于莫比乌斯反演的前缀和和差分意义，使得计算 $g(n) = (f * \mu)(n)$ 时不需要枚举每个 $n$ 的因数 $d$，而只用枚举质因数 $p_i$ 使复杂度略微下降。 |
| ===== 总结 ===== | ===== 总结 ===== | ||
| - | 莫比乌斯反演基本上离不开 GCD 和两个累和符号，而且通常通过将式子化为 $\varepsilon(n)$ 的形式，进而反演成 $\mu(n)$ 并提出相关变量的形式，简化式子进行计算。求解一般通过**数论分块**和预处理 $\mu(n)$ 前缀和的方式在 $\mathcal{O}(\sqrt{n})$ 时间内求和。 | + | 莫比乌斯反演基本上离不开 GCD 和两个累和符号，而且通常通过将式子化为 $\varepsilon(n)$ 的形式，进而反演成 $\mu(n)$ 并提出相关变量的形式，简化式子进行计算。求解一般通过**数论分块**和预处理 $\mu(n)$ 前缀和的方式在 $O(\sqrt{n})$ 时间内求和。 |
| - | * $\epsilon = \mu \times 1$，$n = \varphi \times 1$ | + | * $\varepsilon = \mu * 1$，$n = \varphi * 1$ |
| * 当待分块函数（如 $\mu$）可以单独提出**预处理**时，可以通过此降低时间复杂度。 | * 当待分块函数（如 $\mu$）可以单独提出**预处理**时，可以通过此降低时间复杂度。 | ||
| * 若多次询问中，分块区域下含有 GCD 的枚举值 $g$ 和 $i$ 或 $j$ 之一，可以通过更换枚举变量改为枚举 $ig$ 或 $jg$ 的值，再枚举 $g$ 加速。（说法很意识流，详见[[https://blog.sengxian.com/algorithms/mobius-inversion-formula|莫比乌斯反演简要笔记 - GCD的幂]]） | * 若多次询问中，分块区域下含有 GCD 的枚举值 $g$ 和 $i$ 或 $j$ 之一，可以通过更换枚举变量改为枚举 $ig$ 或 $jg$ 的值，再枚举 $g$ 加速。（说法很意识流，详见[[https://blog.sengxian.com/algorithms/mobius-inversion-formula|莫比乌斯反演简要笔记 - GCD的幂]]） | ||
2020-2021/teams/i_dont_know_png/nikkukun/mobius_inversion.1589273354.txt.gz · 最后更改: 2020/05/12 16:49 由 nikkukun
