主要思路
虽然是个套路题，但是为了完全体会 min-max 反演的魅力之处，我决定写篇博客来强化一下。
先写出答案的式子：
\[ \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]} \]
二项式反演的主要内容就是：
\[ f_n = \sum_{i = 0}^n (-1)^i {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^i {n \choose i} f_i \]
这个反演的式子非常的优美：在这种形式下，它们是对称的。当然，亦可以写作：
\[ f_n = \sum_{i = 0}^n {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^{n – i} {n \choose i} f_i \]
这道题还是比较有意思的（啊呀看了好久的题解才会写，真菜），主要就是把\(d\)转换成了：
\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]
可以感性理解一下：每一次约数被枚举出来的时候，只有互质的情况下才会被计数，避免了重复计数。 Continue reading →