此题的推导中,出现了这样的变形
∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd(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)∑i=1⌊kn⌋∑j=1⌊km⌋∑d∣gcd(i,j)μ(d)
然后变成了
∑d=1n∑i=1⌊nkd⌋∑j=1⌊mkd⌋μ(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)∑d=1n∑i=1⌊kdn⌋∑j=1⌊kdm⌋μ(d)
题解的解释是 这样就不用考虑 ddd 是否为 gcd(i,j)\gcd(i, j)gcd(i,j) 的因数。
对这一步不是非常理解,为啥这样能保证 ddd 为 gcd(i,j)\gcd(i, j)gcd(i,j) 的因数了?