題意
https://www.luogu.org/problem/P3312
題解
顯然就是求 $\sum_{i=1}^{n} \sum_{j=1}^{m} \sigma_1(\gcd{(i,j)})\times [gcd(i,j)\le a]$（$\sigma_1(x)$ 表示求 $x$ 的所有約數之和），看到 $gcd$ 就知道是莫比烏斯反演基礎題吧
如果不考慮 $a$ 的限制，這就是推一遍莫反的模闆題，那先不考慮
原式變為$$\sum_{i=1}^{n} \sum_{j=1}^{m} \sigma_1(\gcd{(i,j)})$$
根據套路枚舉約數 $$\sum_{d=1}^{n} \sum_{i=1}^{n} \sum_{j=1}^{m} \sigma_1(d)\times [gcd(i,j)=d]$$
把 $\sigma_1$ 挪到前面，并用經典公式 $\sum_{d|n} \mu{(d)} = [n=1]$ 對最後的一個 sigma 反演 $$\sum_{d=1}^{n} \sigma_1(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} \sum_{d|\gcd{(i,j)}} \mu(d)$$
$$\sum_{d=1}^{n} \sigma_1(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor} \sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} \sum_{d|i, d|j} \mu(d)$$
把 $x$ 挪到前面
轉載于:https://www.cnblogs.com/scx2015noip-as-php/p/luogu3312.html