莫比乌斯反演

一个小题

先讲一个同学出的题了解一下一种数论变换方式
给定 $n(n\leq 10^6)$ ,求
$$ \prod_{i=1}^{n}\prod_{j=1}^{n}\frac{lcm(i,j)}{gcd(i,j)} $$
虽然有 $\mathcal{O(n)}$ 的方法,但是这里不提了
考虑式子化简
$$\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{lcm(i,j)}{gcd(i,j)}$$
$$ =\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{i\cdot j}{gcd^2(i,j)}=\frac{\prod_{i=1}^{n}\prod_{j=1}^{n}i\cdot j}{\prod_{i=1}^{n}\prod_{j=1}^{n}gcd^2(i,j)} $$
上面很好处理,于是考虑下面怎么求
继续阅读