题解 SP5971 【LCMSUM - LCM Sum】

· · 题解

考察

\sum_{i=1}^{n} lcm(i,n)=\sum_{i=1}^{n} in/gcd(i,n) =n\sum_{i=1}^{n} i/gcd(i,n)

那我们可以计算对于每个d作为gcd(i,n)时，它对答案的贡献，就有

=n\sum_{d|n}\sum_{i=1}^{n} \frac{i}{d}[gcd(i,n)==d]

考虑到如果gcd(i,n)==d，必然有i为d的倍数，因此不妨将i的意义转化为原来的i/d,也即

=n\sum_{d|n}\sum_{i=1}^{n/d} \frac{i}{d}[gcd(id,n)==d] =n\sum_{d|n}\sum_{i=1}^{n/d} i[gcd(i,n/d)==1] =n\sum_{d|n}\sum_{i=1}^{d} i[gcd(i,d)==1]

注意到\sum_{i=1}^{d} i[gcd(i,d)==1]表示[1,d]中与d互质的数的和，它等于\frac{\varphi(d)d}{2}(当d=1时为1)。证明如下：

当d>1时，\varphi(d)总是偶数，这是因为与d互质的数总是成对出现。具体来说，假如i与d互质，d-i与d肯定也互质，它们的和是d，并且有\varphi(d)/2对。

于是上式化简为

=n\sum_{d|n}\frac{\varphi(d)d}{2}

设

f(d)=\sum_{d|n}\frac{\varphi(d)d}{2}

那么对于每个1\le d\le n,我们只要把\frac{\varphi(d)d}{2}加到f(dj)中去,询问时再把最外面那个n乘进去。复杂度是O(nlogn+T)