对此题莫反柿子的疑惑
查看原帖
对此题莫反柿子的疑惑
685604
Neovim楼主2023/1/19 18:10

此题的推导中,出现了这样的变形

i=1nkj=1mkdgcd(i,j)μ(d)\sum_{i = 1}^{\left \lfloor \frac{n}{k} \right \rfloor } \sum_{j = 1}^{\left \lfloor \frac{m}{k} \right \rfloor } \sum_{d|\gcd(i, j)} \mu(d)

然后变成了

d=1ni=1nkdj=1mkdμ(d)\sum_{d = 1}^{n} \sum_{i = 1}^{\left \lfloor \frac{n}{kd} \right \rfloor } \sum_{j = 1}^{\left \lfloor \frac{m}{kd} \right \rfloor } \mu(d)

题解的解释是 这样就不用考虑 dd 是否为 gcd(i,j)\gcd(i, j) 的因数。

对这一步不是非常理解,为啥这样能保证 ddgcd(i,j)\gcd(i, j) 的因数了?

2023/1/19 18:10
加载中...