一些挖了却不会填的坑


莫比乌斯反演

首先先看一个并不需要莫比乌斯反演的问题,求$$\sum_{a=1}^N \sum_{b=1}^N \gcd(a,b), \ N \leq 10^7$$将式子变形,转化为枚举最大公约数\(d\)的形式$$\sum_{d = 1}^N d \sum_{i = 1}^{\lfloor \frac Nd \rfloor} \sum_{j = 1}^{\lfloor \frac Nd \rfloor} [\gcd(i,j)=1]$$我们发现这个式子后半部分和欧拉函数\( \varphi(n) \)的定义是类似的。因为数对\( (x,y) \)是有序的,所以当\( x \neq y \)时需要算两遍,答案就是$$\sum_{d = 1}^{N} d(2\varphi(\lfloor \frac nd \rfloor ) – 1)$$
那么再来看一个问题,求$$\sum_{a=1}^N \sum_{b=1}^M \gcd(a,b), \ N \leq \ M \leq 10^7$$对于这道题(也许)需要用到莫比乌斯反演来解决。我们考虑定义\(F(n)\)与\(f(n)\),然后利用莫比乌斯反演公式来进行转换。
我们发现这样定义\(F(n)\)与\(f(n)\)比较友好:$$f(n) = \sum_{i = 1}^N \sum_{j = 1}^M [\gcd(i,j)=n]$$ $$F(n) = \sum_{n|d} \sum_{i = 1}^N \sum_{j = 1}^M [\gcd(i,j)=d]$$其中,\( \sum_{n=1}^N n f(n)\)就是我们要求的答案,\(F(d)\)就是统计所有\(a|d\)且\(b|d\)的合法的数对\( (a,b) \)的个数。那么就有$$F(n) = \lfloor \frac Nn \rfloor \lfloor \frac Mn \rfloor$$于是我们代入前面提到的第二种莫比乌斯反演公式得到$$f(n) = \sum_{n|d} \mu(\frac dn) F(d) = \sum_{n|d} \mu(\frac dn) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor$$此时我们令\(n = 1\),有$$f(1) = \sum_{d = 1}^N \mu(d) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor$$我们利用\( f(1) \) 可以写出任意\( f(n) \)的值:$$f(n) = \sum_{d = 1}^{\lfloor \frac N n \rfloor}\mu(d) \lfloor \frac {\lfloor \frac N n \rfloor } d \rfloor \lfloor \frac {\lfloor \frac M n \rfloor} d \rfloor$$由于要求的东西为\( \sum_{n=1}^N n f(n)\),所以答案是$$\sum_{n=1}^N n \sum_{d = 1}^{\lfloor \frac N n \rfloor } \mu(d) \lfloor \frac {\lfloor \frac N n \rfloor } d \rfloor \lfloor \frac {\lfloor \frac M n \rfloor} d \rfloor$$

这个式子不是我想要的式子但是因为太菜了只能先放在这里了orz……

然后我们就算没证出来翻翻题解也能得到结论,答案就是$$\sum_{d = 1}^N \varphi(d) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor $$
其实欧拉函数有一个性质体现在了答案的式子里$$ n = \sum_{d | n} \varphi (d) $$这个性质还可以通过欧拉函数的定义来证明……证明如下(orz Hoblovski)

如果我们用这个式子推的话有$$
\begin{align*}
\sum_{a=1}^N \sum_{b=1}^M \gcd(a,b) &= \sum_{a=1}^N \sum_{b=1}^M \sum_{d | \gcd(a,b)} \varphi(d) \\
&= \sum_{a=1}^N \sum_{b=1}^M \sum_{d|a, d|b} \varphi(d) \\
&= \sum_d \varphi(d) \sum_{a=1}^N \sum_{b=1}^M [d|i \ and \ d|j] \\
&= \sum_d \varphi(d) \lfloor \frac Nd \rfloor \lfloor \frac Md \rfloor
\end{align*}
$$这样也能得到答案。(orz Euler)