【SPOJ】LCM Sum


题意

求 \(\sum_{i=1}^n lcm(i,n)\) 。

分析

我们并不太会直接求 lcm ,于是考虑转换成 gcd 来做。

\(\sum_{i=1}^n lcm(i,n)\\=\sum _{i=1}^n\frac{in}{gcd(i,n)}\\=\frac{1}{2}(\sum _{i=1}^{n-1}\frac{in}{gcd(i,n)}+\sum _{i=1}^{n-1}\frac{in}{gcd(i,n)})+n\)

对于 gcd 而言,显然有 \(gcd(a,b)=gcd(b-a,b)\) ,于是:

\(\sum_{i=1}^n lcm(i,n)\\=\frac{1}{2}(\sum _{i=1}^{n-1}\frac{in}{gcd(i,n)}+\sum _{i=1}^{n-1}\frac{in}{gcd(n-i,n)})+n\\=\frac{1}{2}\sum_{i=1}^{n-1}\frac{in+(n-i)n}{gcd(i,n)}+n\\=\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)}+n\) .

考虑枚举 \(gcd(i,n)\) 的值,如果 \(gcd(i,n)=d\) ,显然有 \(gcd(\frac{i}{d},\frac{n}{d})=1\) ,那么显然这样的 \(i\) 有 \(\varphi(\frac{n}{d})\) 个。

于是有 \(\sum_{i=1}^n lcm(i,n)\\=\frac{1}{2}\sum_{d|n}\frac{n^2\varphi(\frac{n}{d})}{d}+n\\=\frac{n}{2}\sum_{d|n}d\varphi(d)+n\) .

令 \(g(n)=\sum_{d|n}d\varphi(d)\) ,这部分显然可以通过线性筛预处理出来,于是每次询问就 \(O(1)\) 了。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 61,990

Categories

Archive

Comments