简述
突然记起来 CSP 前特别喜欢的 POI 题还有一堆没写，所以就有了这个坑。
先写出答案的式子：
\[ \prod_{i = 1}^n \prod_{i = 1}^m f(\gcd(i, j)) \]
老套路，枚举公约数：
\[ \prod_{d = 1}^{\min(n, m)} f(d)^{\sum_{i = 1}^n \sum_{j = 1}^m [gcd(i, j) = d]} \]
这道题是一道裸题，考察莫比乌斯反演和 Dirichlet 卷积的知识。
在这里我们规定\(n<m\)，这两者调换不会对答案产生影响。然后我们来观察这个计数规律，发现每一个点对答案的贡献至少为\(1\)，附加的贡献其实就是当前线段上除了本身的整点（整数坐标点）个数的两倍，换句话说就是：
\[ ans = \sum_{i = 1}^n \sum_{j = 1}^m 1 + 2( gcd(i, j) – 1 ) \]
首先规定，\(N<M\)。之后写出统计答案的式子：
\[ \sum_{i=1}^N \sum_{j=1}^M lcm(i,j) \\ \sum_{i=1}^N \sum_{j=1}^M \frac{ij}{\gcd(i,j)} \]
然后我们可以试着去枚举最大公约数\(gcd(i,j)=d\)，然后让\(i,j\)成为唯一的两个互质因子。
这道题还是比较有意思的（啊呀看了好久的题解才会写，真菜），主要就是把\(d\)转换成了：
\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]
可以感性理解一下：每一次约数被枚举出来的时候，只有互质的情况下才会被计数，避免了重复计数。 Continue reading →