一个经典问题
求
[sum_{k=1}^nmathbb{lcm}(k,n)
]
一般的做法是使用(varphi(n))函数。
不经典的做法
[egin{align*}
sum_{k=1}^nmathbb{lcm}(k,n)
&=sum_{k=1}^nfrac{nk}{gcd(n,k)} ag{gcd与lcm的关系}\
&=sum_{d|n}sum_{k=1}^{n/d}frac{ndk}{d}[gcd(n,dk)=d] ag{枚举gcd(n,k)}\
&=sum_{d|n}sum_{k=1}^{n/d}nk[gcd(frac{n}{d},k)=1] ag{同消去d}\
&=nsum_{d|n}sum_{k=1}^dk[gcd(d,k)=1] ag{用d代替n/d}\
&=nsum_{d|n}sum_{k=1}^dksum_{j|gcd(d,k)}mu(j) ag{莫比乌斯函数的性质}\
&=nsum_{j|n}mu(j)sum_{d|n/j}sum_{k=1}^djk ag{交换求和次序}\
&=nsum_{j|n}mu(j)jsum_{d|n/j}frac{d(d+1)}{2} ag{等差数列求和公式}\
&=frac{n}{2}left(sum_{j|n}mu(j)jsum_{d|n/j}d^2+sum_{j|n}mu(j)jsum_{d|n/j}d
ight) ag{拆分}\
&=frac{n}{2}(f(n)+g(n)) ag{设元}\
end{align*}
]
计算(f(n))
考虑
[f(n)=sum_{j|n}mu(j)jsum_{d|n/j}d^2
]
易证(mu(j)j)和(sumlimits_{d|n}d^2)都是积性函数。
则(f(n))为积性函数(mu(j)j)和(sumlimits_{d|n}d^2)的狄利克雷卷积，可得(f(n))为积性函数。
则(f(n))可用欧拉筛法求出如下：
[egin{align*}
f(p^k)
&=mu(1)sum_{d=0}^k(p^d)^2+mu(p)psum_{d=0}^{k-1}(p^d)^2 ag{莫比乌斯函数的性质}\
&=sum_{d=0}^kp^{2d}-sum_{d=0}^{k-1}p^{2d+1} ag{整理}\
&=sum_{d=0}^{2k}(-p)^k ag{合并}\
&=frac{1-(-p)^{2k+1}}{1+p} ag{等比数列求和公式}\
&=frac{1+p^{2k+1}}{1+p} ag{整理}\
end{align*}
]
再维护一个最小质因数的次数(p^k)即可。
计算(g(n))
考虑
[g(n)=sum_{j|n}mu(j)jsum_{d|n/j}d
]
同上，可得(g(n))为积性函数。
则(g(n))可
用欧拉筛法求出如下：
[egin{align*}
g(p^k)
&=mu(1)sum_{d=0}^kj^d+mu(p)psum_{d=0}^{k-1}j^d ag{莫比乌斯函数的性质}\
&=sum_{d=0}^kj^d-sum_{d=1}^{k}j^d ag{整理}\
&=1 ag{展开}\
end{align*}
]
我们可以惊讶地发现(g(n))恒等于(1)！
总结
则我们可以每次(O(1))地求出
[sum_{k=1}^nmathbb{lcm}(k,n)=frac{n}{2}(f(n)+1)
]