GCD of Divisors

\[
\bigstar \fbox{此题极难。全世界通过者不足200人。慎入。}
\]

Problem Description

每个\(n \)的因子\(d\)都有它的对偶因子\(\dfrac{n}{d}\)

设\(f(n)\)是\(n\)的所有正除数\(d\)和\(\dfrac{n}{d}\)的最大公约数之和,即\(\displaystyle f(n)=\displaystyle\sum\limits_{d|n}\, \text{gcd}(d,\frac n d)\)

令\(F\)为\(f\)的和,也就是\(\displaystyle F(k)=\displaystyle\sum\limits_{n=1}^k \, f(n)\)

已知\(F(10)=32,  F(1000)=12776\)

求\(F(10^{15})\)

Solution

此题的难点就在于公式难推导,需要拐好几个弯。重点的地方都已经加粗表示,希望读者认真体会

这个范围显然杜教筛也是做不了的,而且考虑直接化简\(f(n)\)也遇到了困难,所以考虑将前缀和的\(\sum\)一起化简

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

这一步很常见的是第一重和式改为枚举倍数,但这样化简后面就推不下去了。

想到这种题通常的做法都要化成\( \sigma_0(n)\)的形式(有gcd,又需要是积性函数)

还是用套路,直接枚举gcd值

\[ F(n)=\sum_{d=1}^{n}d\sum_{i=1}^{n}\sum_{g|i}\left [ \left (g,\frac{i}{g} \right)=d \right ] \]

这里有\( \displaystyle \left (g,\frac{i}{g} \right)=d\),说明\(i\)中必须至少包含\(2\)个\(d\),那么令,\(g\)即可任取\(i\)的因子,最终的\(g\)和\(\dfrac{i}{g}\)各乘\(d\)即可,所以可以进行如下化简

\[ F(n)=\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d^2}}\sum_{g|i}\left[ \left (g,\frac{i}{g} \right )=1 \right ]\]

看起来不像可以转化为\( \varphi\)

……

好像卡住了!算了,直接使出绝招—莫比乌斯反演!

\[F(n)=\sum_{d=1}^{n}d\sum_{i=1}^{\frac{n}{d^2}}\sum_{g|i}\sum_{d’|g \cap d’|\frac{i}{g}}\mu(d’) \\
F(n)=\sum_{d=1}^{n}\sum_{d’=1}^{n}d \circ \mu(d’)\sum_{i=1}^{\frac{n}{d^2}}\sum_{g|i}[d’|g \cap d’|\frac{i}{g}]\]

这里和上面一样,都是要求\(d’|g\)并且\(d’|\dfrac{i}{g}\),因此从\(i\)中提取\(2\)\(d’\),即令\(i=\dfrac{i}{d’^2}\)。

\[ F(n)=\sum_{d=1}^{n}\sum_{d’=1}^{n}d \circ \mu(d’)\sum_{i=1}^{\frac{n}{(dd’)^2}}\sum_{g|i}1\]

会发现后面是约数个数。

\[ F(n)=\sum_{d=1}^{n}\sum_{d’=1}^{n}d \circ \mu(d’)\sum_{i=1}^{\frac{n}{(dd’)^2}}\sigma_0(i)\]

前面部分发现\(d \circ μ(d’)\)可以卷积到\(\varphi\),考虑合并\(dd’\)来构造卷积,令\(d=dd’\)

\[ F(n)=\sum_{d=1}^{\sqrt{n}}\sum_{g|d}g \circ \mu \left (\frac{n}{g} \right )\sum_{i=1}^{\frac{n}{(dd’)^2}}\sigma_0(i) \]

为什么只枚举到\( \sqrt{n}\),因为\( d> \sqrt{n}\)之后的\( \sum=0\)没有贡献。因此可以缩小实际枚举范围

然后根据狄利克雷卷积\(\mu \circ \text{N} =\varphi(N(n)=n)\)可以化简

\[ F(n)=\sum_{d=1}^{\sqrt{n}}\varphi(d)\sum_{i=1}^{\frac{n}{(dd’)^2}}\sigma_0(i)\]

其中,约数个数的前缀和可以进行分块取值优化,如下

\[ \sum_{i=1}^{n}\sigma_0(i)=\sum_{i=1}^{n}\sum_{d|i}1=\sum_{i=1}^{n}\sum_{j=1}^{\frac{n}{i}}1 \\
\sum_{i=1}^{n}\sigma_0(i)=\sum_{i=1}^{n}\left \lfloor \frac{n}{i} \right \rfloor
\]

然后线性筛\( \varphi\)的过程中求解即可

\[ O \left (\sum_{i=1}^{\sqrt{n}}\sqrt{\frac{n}{i^2}}\right ) = O \left (\sum_{i=1}^{\sqrt{n} }\frac{\sqrt{n}}{i} \right)= O \left (\int_{1}^{\sqrt{n} }\frac{\sqrt{n}}{i} \text{d} i \right) = O \left (\sqrt{n} \ln \sqrt{n} \right )\]

0