莫比乌斯反演-例题

由于之前那篇备忘录要是再加上例题就太长了,所以单独开了一篇
可以先看一下前一篇文章
下文中默认 $n<m$

一个常见的套路

求 $n$ 以内和 $m$ 以内互质数对个数
$$
\begin{eqnarray}
&&\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) \\
&=&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d=1}^{n}\mu(d)\times [d\mid gcd(i,j)] \\
&=&\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n}\sum_{j=1}^{m}[d\mid gcd(i, j)] \\
&=&\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[1\mid gcd(i,j)]\\
&=&\sum_{d=1}^{n}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor
\end{eqnarray}
$$
继续阅读

莫比乌斯反演

一个小题

先讲一个同学出的题了解一下一种数论变换方式
给定 $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)} $$
上面很好处理,于是考虑下面怎么求
继续阅读