链接:lg3455
题解
- $ans=\sum_{i}^a{\sum_{j=1}^b{gcd(i,j)=d}}$
- $ans=\sum_{i}^{\frac ad}{\sum_{j=1}^{\frac bd}{gcd(i,j)=1}}$
- $ans=\sum_{i}^{\frac ad}{\sum_{j=1}^{\frac bd}{\sum_{x|gcd(i,j)}^{}{\mu(x)}}}$
- $ans=\sum_{x}^{min(\frac ad,\frac bd)}{\mu(x) \cdot \sum_{i}^{\frac ad}{\sum_{j}^{\frac bd}{x|gcd(i,j)}}}$
- 枚举ix jx
- $ans=\sum_(x)^{min(\frac ad,\frac bd)}{\mu(x) \cdot \sum_{i}^{\frac a{dx}}{\sum_{j}^{\frac b{dx}}}}$
- $ans=\sum_(x)^{min(\frac ad,\frac bd)}{\mu(x) [\frac a{dx}]\cdot [\frac b{dx}]}$
- 这样就可以O(n)做出来了,但是还是会T,这里用下除法分块就可以在O($\sqrt n$)做出来
1 |
|