莫比乌斯函数
设 \(x\in N\) 唯一分解后为 \(x\ =\ p_1^{c_1}p_2^{c_2}p_3^{c_3}\cdots p_n^{c_n}\)
我们定义莫比乌斯函数
\[ \mu(x)\ = \
\begin{cases}
0&\exists\ c_i > 1\\\\
-1&n\ \equiv\ 1\ (\ mod\ 2\ )\\\\
1&n\ \equiv\ 0\ (\mod\ 2\ )
\end{cases}
\] 通过观察定义，稍有常识的人 除了我
都能看出这是个积性函数，并且我们对莫比乌斯函数分析也通常是对唯一分解后的素数集合进行分析，这也是分析一般积性函数的一般方法
通过 口胡 打表 正经分析
得出对于莫比乌斯函数的积性函数的递推式
\[ \mu(np)\ = \ \begin{cases} 0&\ n \perp p\\\\ -\mu(n)&\ n \not\perp p \end{cases} \]
那么，欧拉筛莫比乌斯函数有如下操作
1 | void sieve(int d) |
莫比乌斯反演
蒟蒻一直学的是的假莫反
莫比乌斯反演通常表现为
\[ \begin{aligned} &g(x)\ =\ \sum_{d|x}f(d)\\\\ &f(x)\ =\ \sum_{d|x}\mu(\frac{x}{d})g(d) \end{aligned} \]
或
\[ \begin{aligned} &g(x)\ =\ \sum_{x|d}^{n}f(d)\\\\ &f(x)\ =\ \sum_{x|d}^{n}\mu(\frac{d}{x})g(d) \end{aligned} \]
可是蒟蒻都不会用
所以一直使用莫比乌斯函数，而是使用这一个性质
\[ \begin{aligned} [\ x = 1\ ]\ =\ \sum_{d|x}\mu(d) \end{aligned} \]
下面给出这个性质的证明
我们考虑在只有枚举 \(d\) 满足 \(d\ =\ p_1^{c_1}p_2^{c_2}p_3^{c_3}\cdots p_n^{c_n},\ \forall c < 2\) 时才会对答案产生贡献
所以有
\[ \begin{aligned} \sum_{d|x}\mu(d)\ =\ \sum_{i\ =\ 0}^n(-1)^{i+1}\tbinom{i}{n} \end{aligned} \]
则有
\[\sum_{d|x}\mu(d)\ =\ \begin{cases} 1&n\ =\ 1\\\\ 0&n\ \neq\ 1\\ \end{cases} =\ [x\ =\ 1] \]
例题
例题中的 n 均小于 m，p是质数集合任意一个元素
暂无裸题
\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[gcd(i,\ j)\ =\ 1] \end{aligned} \]
根据性质
\(\sum_{i=1}^n\sum_{j=1}^m[gcd(i,\ j)\ =\ 1] \ =\ \sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,\ j)}\mu(d)\)
把 \(d|gcd(i,\ j)\) 拆开
\(\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,\ j)} =\ \sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,\ d|j}\mu(d)\)
更改枚举形式，把条件写在和式右端，并根据条件扩大枚举范围
\(\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,\ d|j}\mu(d)\ =\ \sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^n\mu(d)[d|i][d|j]\)
交换和式
\(\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^n\mu(d)[d|i][d|j]\ =\ \sum_{d=1}^n\mu(d)\sum_{i=1}^n[d|i]\sum_{j=1}^m[d|j]\)
发现实际上为枚举约数个数
\(\sum_{d=1}^n\mu(d)\sum_{i=1}^n[d|i]\sum_{j=1}^m[d|j]\ =\ \sum_{d=1}^n\mu(d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor\)
P2522 [HAOI2011]Problem b
\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[gcd(i,\ j)\ =\ k] \end{aligned} \]我们把所有满足条件的 \(gcd(i,\ j)\) 剔除约数 \(k\) 实际上相当于求
\[ \begin{aligned} \sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}[gcd(i,\ j)\ =\ 1] \end{aligned} \]
所以 \[ \begin{aligned} \sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}[gcd(i,\ j)\ =\ 1] =\ \sum_{d=1}^{\lfloor \frac{n}{k}\rfloor}\mu(d)\lfloor \frac{n}{kd}\rfloor \lfloor \frac{m}{kd}\rfloor \end{aligned} \]暂无裸题
\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^mij[gcd(i,\ j)\ =\ k] \end{aligned} \]与上题一样，我们把所有满足条件的 \(gcd(i,\ j)\) 剔除约数 \(k\) 实际上相当于求
\[ \begin{aligned} \sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}ij[gcd(i,\ j)\ =\ 1]\ k^2 \end{aligned} \]
注意此时虽然我们把所有数剔除 \(k\) 后，依然需要累加贡献
\[ \begin{aligned} \sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}ij[gcd(i,\ j)\ =\ 1]\ k^2\ &=\ k^2\sum_{d=1}^{\lfloor \frac{n}{k}\rfloor}\mu(d)\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k}\rfloor}ij[d|i][d|j] \end{aligned} \]
观察后面的和式，把 \(d\) 提出即变成等差数列
\[ \begin{aligned} k^2\sum_{d=1}^{\lfloor \frac{n}{k}\rfloor}\mu(d)*d^2\sum_{i=1}^{\lfloor \frac{n}{kd}\rfloor}i\sum_{j=1}^{\lfloor \frac{m}{kd}\rfloor}j \end{aligned} \]P1447 [NOI2010]能量采集
\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^mgcd(i,\ j) \end{aligned} \]这道题虽然可以根据欧拉函数性质直接得出
\[ \begin{aligned} x \ =\ \sum_{d|x}\phi(d) \end{aligned} \]
从而
\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^mgcd(i,\ j)\ =\ \sum_{d=1}^n\phi(d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor \end{aligned} \]
但用莫比乌斯函数推导会更有意义一些
我们枚举 \(gcd(i,\ j)\) 得到
\(\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^m[gcd(i,\ j)\ =\ d]\)
后面根据前文，化简为
\(\sum_{d=1}^nd\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor\)
设 \(T = kd\) 则有
\(\sum_{d=1}^nd\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor\ =\ \sum_{d=1}^nd\sum_{T=1}^n\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T}\rfloor[d|T]\ =\ \sum_{T=1}^n\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T}\rfloor\sum_{d|T}\mu(\frac{T}{d})d\)
设 \(F(n)\ =\ \sum_{d|n}\mu(\frac{n}{d})d\) ，并考虑在欧拉筛过程中求出
下面是一个很重要的技巧，考虑加入 \(p\) 对于原来的约数集合的影响则有
\(F(np)\ =\ \sum_{d|n}\mu(\frac{np}{d})d+\sum_{d|n}\mu(\frac{np}{dp})dp\)
当 \(n\ \perp\ p\) 时，\(\sum_{d|n}\mu(\frac{np}{d})d+\sum_{d|n}\mu(\frac{np}{dp})dp\ =\ -F(n)+pF(n)\)
当 \(n\ \not\perp\ p\) 时，\(\sum_{d|n}\mu(\frac{np}{d})d+\sum_{d|n}\mu(\frac{np}{dp})dp\ =\ pF(n)\)
综上，
\[ F(np)\ = \ \begin{cases} (p-1)F(n)&\ n \perp p\\\\ pF(n)&\ n \not\perp p\\ \end{cases} \]
我们发现这恰好是 \(\phi(n)\) 的递推式，因此是正确的
这样推式子是一种套路，请仔细思考P2257 YY的GCD
\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[\ gcd(i,\ j)\ =\ p\ ] \end{aligned} \]
我们设有函数 \(f(n)\ =\ [n\ =\ p]\)
则题意变为
\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^mf(gcd(i,\ j)) \end{aligned} \]
我们枚举 \(gcd(i,\ j)\) 得到
\(\sum_{d=1}^nf(d)\sum_{i=1}^n\sum_{j=1}^m[gcd(i,\ j)\ =\ d]\)
后面根据前文，化简为
\(\sum_{d=1}^nf(d)\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor\)
设 \(T = kd\) 则有
\(\sum_{d=1}^nf(d)\sum_{k=1}^{\lfloor \frac{n}{d} \rfloor}\mu(k)\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor =\sum_{d=1}^nf(d)\sum_{T=1}^n\mu(\frac{T}{d})\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T}\rfloor[d|T] =\sum_{T=1}^n\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T}\rfloor\sum_{d|T}\mu(\frac{T}{d})f(d)\)
设 \(F(n)\ =\ \sum_{d|n}\mu(\frac{n}{d})f(d)\) ，并考虑在欧拉筛过程中求出
考虑加入 \(p\) 对于原来的约数集合的影响则有
\(F(np)\ =\ \sum_{d|n}\mu(\frac{np}{d})f(d)+\sum_{d|n}\mu(\frac{np}{dp})f(dp)\)
当 \(n\ \perp\ p\) 时，\(\sum_{d|n}\mu(\frac{np}{d})f(d)+\sum_{d|n}\mu(\frac{np}{dp})f(dp)\ =\ -F(n)+\mu(n)\)
当 \(n\ \not\perp\ p\) 时，\(\sum_{d|n}\mu(\frac{np}{d})f(d)+\sum_{d|n}\mu(\frac{np}{dp})f(dp)\ =\ \mu(n)\)
综上，
\[ F(np)\ = \ \begin{cases} -F(n)+\mu(n)&\ n \perp p\\\\ \mu(n)&\ n \not\perp p\\ \end{cases} \]
我们发现这道和上一道有许多复读的部分，总结一下发现如果有一道题可以表示为
\[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^mf(gcd(i,\ j)) \end{aligned} \]
实际上就是求出
\[ \begin{aligned} \sum_{T=1}^n\lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T}\rfloor\sum_{d|T}\mu(\frac{T}{d})f(d) \end{aligned} \]
并且按照上面的技巧讨论即可