解法
好题。
我们首先写出这道题的暴力解:
\[ answer = \sum_{i = 1}^n \sum_{j = 1}^m \sigma_1 (gcd(i, j)) [\sigma_1 (gcd(i, j)) \leq limit] \]
复杂度超级大,怎么办?换一种思维来写这个式子,考虑枚举每一个\(gcd(i, j)\)为\(d\),记起次数为\(g(d)\),我们可以搞出并化简为:
好题。
我们首先写出这道题的暴力解:
\[ answer = \sum_{i = 1}^n \sum_{j = 1}^m \sigma_1 (gcd(i, j)) [\sigma_1 (gcd(i, j)) \leq limit] \]
复杂度超级大,怎么办?换一种思维来写这个式子,考虑枚举每一个\(gcd(i, j)\)为\(d\),记起次数为\(g(d)\),我们可以搞出并化简为: