计算 gcd(i,j)=k 的对数

计算 \(\gcd(i,j)=k\) 的对数

Problem

\[\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] \]

Solution

设 \(f(k)\) 表示 \(\gcd(i,j)==k\) 的对数(即答案),\(g(k)\) 表示 \(k|\gcd(i,j)\) 的对数

根据 \(g\) 的定义,我们知道:\(g(k)=\lfloor\frac nk\rfloor\lfloor\frac mk\rfloor\)

而且显然有 \(g(k)=\sum_{i=1}^{\frac nk}f(i\times k)\)

根据莫比乌斯反演,我们得到:

\[f(k)=\sum_{i=1}^{\frac nk}g(i\times k)\mu(i)=\sum_{i=1}^{\frac nk}\mu(i)\lfloor\frac nk\rfloor\lfloor\frac mk\rfloor \]

这样,我们可以用整除分块 $\max(\sqrt m,\sqrt n) $ 处理 \(\lfloor\frac nk\rfloor\lfloor\frac mk\rfloor\)

上一篇:P6269 [SHOI2002]空中都市 题解


下一篇:微信小程序获取用户手机号详解