对Arahc的数论博客的个人解释

记载一下自己推的比较艰难的式子。

数论选讲

1）欧拉函数不常用的性质中的第二条和第三条暂无证明，直接用就好了...；
2）$f ∗ \varepsilon = f$

根据核心公式可以转换为：

$\sum\limits_{d \mid n}f(d) \varepsilon( \frac{n}{d} )$

感性理解一下：有且仅有在$d = n$时，$\varepsilon(1) = 1$，此时的$f(n)$才会记载入$f$数组；而$n$就是$f$函数的长度啦。

3）最后一长串式子：

$\begin{aligned} Ans&=\sum\limits_{i=1}^\frac{x}{k}\sum\limits_{i=1}^{\frac{y}{k}}\sum\limits_{d\mid\gcd(i,j)}\mu(d) \\ &=\sum\limits_{d=1}^{\min(\frac{x}{k},\frac{y}{k})} \sum\limits_{d\mid i}^{\frac{x}{k}}\sum\limits_{d\mid j}^{\frac{y}{k}}\mu(d) \\ &=\sum\limits_{d=1}^{\min(\frac{x}{k},\frac{y}{k})}\mu(d) \sum\limits_{d\mid i}^{\frac{x}{k}}\sum\limits_{d\mid j}^{\frac{y}{k}}*1 \\ &=\sum\limits_{d=1}^{\frac{\min(x,y)}{k}}\mu(d)\lfloor\frac{x}{kd}\rfloor\lfloor\frac{y}{kd}\rfloor \\ \end{aligned}$

第二行：枚举能被$i,j$整除的$d$
第三行：枚举能整除$d$的$i,j$，而这样的$i,j$一共有$\left \lfloor \frac{x}{kd}\right \rfloor$或$\left \lfloor\frac{y}{kd}\right \rfloor$个！
于是就有了第四行。