这只小蒟蒻做莫比乌斯反演的练习题时用$\LaTeX$打了一些草稿,又不舍得扔掉,于是放在这个博客里供大家欣(tu)赏(cao)。
$$\text{求}\sum_{x=1}^n\sum_{y=1}^m[gcd(x,y)\in prime]$$
$$=\sum_{p\in prime}\sum_{x=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{p}\rfloor}[gcd(x,y)=1]$$
$$=\sum_{p\in prime}\sum_{x=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|gcd(x,y)}\mu(d)$$
$$=\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\sum_{p\in prime}\sum_{x=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{p}\rfloor}[d|gcd(x,y)]$$
$$=\sum_{p\in prime}\sum_{d=1}^{\lfloor\frac{n}{p}\rfloor}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor$$