一个经典问题

求
\[
\sum_{k=1}^n\mathbb{lcm}(k,n)
\]

一般的做法是使用\(\varphi(n)\)函数。

不经典的做法

\[
\begin{align*}
\sum_{k=1}^n\mathbb{lcm}(k,n)
&=\sum_{k=1}^n\frac{nk}{\gcd(n,k)}\tag{gcd与lcm的关系}\\
&=\sum_{d|n}\sum_{k=1}^{n/d}\frac{ndk}{d}[\gcd(n,dk)=d]\tag{枚举gcd(n,k)}\\
&=\sum_{d|n}\sum_{k=1}^{n/d}nk[\gcd(\frac{n}{d},k)=1]\tag{同消去d}\\
&=n\sum_{d|n}\sum_{k=1}^dk[\gcd(d,k)=1]\tag{用d代替n/d}\\
&=n\sum_{d|n}\sum_{k=1}^dk\sum_{j|gcd(d,k)}\mu(j)\tag{莫比乌斯函数的性质}\\
&=n\sum_{j|n}\mu(j)\sum_{d|n/j}\sum_{k=1}^djk\tag{交换求和次序}\\
&=n\sum_{j|n}\mu(j)j\sum_{d|n/j}\frac{d(d+1)}{2}\tag{等差数列求和公式}\\
&=\frac{n}{2}\left(\sum_{j|n}\mu(j)j\sum_{d|n/j}d^2+\sum_{j|n}\mu(j)j\sum_{d|n/j}d\right)\tag{拆分}\\
&=\frac{n}{2}(f(n)+g(n))\tag{设元}\\
\end{align*}
\]

计算\(f(n)\)

考虑
\[
f(n)=\sum_{j|n}\mu(j)j\sum_{d|n/j}d^2
\]
易证\(\mu(j)j\)和\(\sum\limits_{d|n}d^2\)都是积性函数。

则\(f(n)\)为积性函数\(\mu(j)j\)和\(\sum\limits_{d|n}d^2\)的狄利克雷卷积，可得\(f(n)\)为积性函数。

则\(f(n)\)可用欧拉筛法求出如下：
\[
\begin{align*}
f(p^k)
&=\mu(1)\sum_{d=0}^k(p^d)^2+\mu(p)p\sum_{d=0}^{k-1}(p^d)^2\tag{莫比乌斯函数的性质}\\
&=\sum_{d=0}^kp^{2d}-\sum_{d=0}^{k-1}p^{2d+1}\tag{整理}\\
&=\sum_{d=0}^{2k}(-p)^k\tag{合并}\\
&=\frac{1-(-p)^{2k+1}}{1+p}\tag{等比数列求和公式}\\
&=\frac{1+p^{2k+1}}{1+p}\tag{整理}\\
\end{align*}
\]

再维护一个最小质因数的次数\(p^k\)即可。

计算\(g(n)\)

考虑
\[
g(n)=\sum_{j|n}\mu(j)j\sum_{d|n/j}d
\]
同上，可得\(g(n)\)为积性函数。

则\(g(n)\)可

用欧拉筛法求出如下：
\[
\begin{align*}
g(p^k)
&=\mu(1)\sum_{d=0}^kj^d+\mu(p)p\sum_{d=0}^{k-1}j^d\tag{莫比乌斯函数的性质}\\
&=\sum_{d=0}^kj^d-\sum_{d=1}^{k}j^d\tag{整理}\\
&=1\tag{展开}\\
\end{align*}
\]
我们可以惊讶地发现\(g(n)\)恒等于\(1\)！

总结

则我们可以每次\(O(1)\)地求出
\[
\sum_{k=1}^n\mathbb{lcm}(k,n)=\frac{n}{2}(f(n)+1)
\]

巴特西

莫比乌斯反演求LCM的另一种做法

一个经典问题

不经典的做法

计算\(f(n)\)

计算\(g(n)\)

总结

最新文章

热门文章