以前写的有点问题,不够普适。

$\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1]&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum_{d|\gcd(i,j)} \mu(d) \end{aligned}$

其中 $\sum\limits_{d|\gcd(i,j)} \mu(d)=\begin{cases}1~~~~~~~&\gcd(i,j)=1\\0&\gcd(i,j)\ne 0\end{cases}$

证明:

$n=\gcd(i,j)={c_1}^{p_1}{c_2}^{p_2}{c_3}^{p_3}\cdots{c_r}^{p_r}$

根据定义,其中有贡献的$d$有 $2^r$个。

转化成组合数就是 $\tbinom{0}{r},\tbinom{1}{r},\cdots,\tbinom{r}{r}$

转化成二项式定理即可得证。

于是可以得出 $\sum\limits_{d|\gcd(i,j)}\mu(d)=[\gcd(i,j)=1]$。

接着上文的式子

$\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1]&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum_{d\mid \gcd(i,j)} \mu(d) \\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum_{d\mid i,d\mid j} \mu(d)\\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum_{d\mid i}[d\mid j] \mu(d)\\&=\sum\limits_{i=1}^n\sum_{d\mid i}\sum\limits_{j=1}^m[d\mid j] \mu(d)\\&=\sum\limits_{i=1}^n\sum_{d\mid i}\sum\limits_{j=1}^m[d\mid j] \mu(d)\end{aligned}$

$[d\mid j]$ 为一个bool值表达式。

以 $d$ 为变量进行观察,那么 $j\in[1,m]$ 中,$d\mid j$ 出现的次数为 $\lfloor\frac{m}{d}\rfloor$ 。

$\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1]&=\sum\limits_{i=1}^n\sum_{d\mid i}\lfloor\frac{m}{d}\rfloor\mu(d) \end{aligned}$

同样地,可以 $\sum_{d\mid i}$ 改写为 $\sum_{d=1}^{\min(n,m)}[d\mid i] $

于是最终可以化简为

$\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=1]&=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\end{aligned}$

最后套一下数论分块。