题意：给定 \(n,k \le 10^9\)，求 \(\sum\limits_{i=1}^n\operatorname{lcm}(i, k) \bmod (10^9+7)\) 的值。
定义 \(f(x,y) = \sum\limits_{i=1}^x[\gcd(i,y)=1]i\)。
容易知道答案 \(res=k\sum\limits_{d|k}f(\lfloor\frac{n}{d}\rfloor, \frac{k}{d})\)。
转化为求 \(f(x,y)\) 的值。
\[f(x,y)=\sum\limits_{i=1}^xi[\gcd(i, y)=1] \]\[=\sum\limits_{i=1}^xi\sum\limits_{d}[d|\gcd(i,y)]\mu(d) \]\[=\sum\limits_{d|y}\mu(d)\sum\limits_{i=1}^x[d|\gcd(i,y)]i \]\[=\sum\limits_{d|y}\mu(d)d\sum\limits_{i=1}^{\lfloor\frac{x}{d}\rfloor}i \]然后枚举 \(d\) 就做完了，时间复杂度 \(O(d^2(k))\)，可以通过。
标签：lfloor,ABC020D,Rush,frac,gcd,limits,sum,mu,LCM From： https://www.cnblogs.com/cjoierzdc/p/17380755.html