【GDOI2016】互补约数 题解

题目大意

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

【20%】$n \le 10^5$

  暴力枚举 $i$，然后根号枚举 $d$。
  时间复杂度 $O(n\sqrt n)$

【50%】$n \le 10^7$

  双sigma带gcd的形式考虑反演。

$$\begin{aligned} &\sum_{i=1}^n\sum_{d|i}\gcd(d,\frac{i}{d}) \\ =&\sum_{d=1}^{\sqrt n}d*f(d) \\ &其中f(d)=\sum_{i=1}^n\sum_{j|i}(\gcd(j,\frac{i}{j})==d) \end{aligned}$$

  接下来我们考虑如何快速求 $f(d)$，方法众多，这里介绍一种非Mobius的方法。
  由于$i$分解成两个因数之后，两个因数都要含因子$d$，因此$i$本身应该是$d^2$的倍数。所以我们不枚举$i$，而是直接枚举$ti=\frac{i}{d^2}$，相当于$j$和$\frac{i}{j}$已经同时约去了$d$。所以

$$f(d)=\sum_{ti=1}^{\lfloor \frac{n}{d^2} \rfloor}\sum_{td|ti}(\gcd(td,\frac{ti}{td})==1)$$

  我们现在其实是把 $ti$ 分解成两个因数，然后两个因数互质。考虑将 $ti$ 分解质因数，那么对于 $ti$ 的同一种质因子，$td$ 要么将它全选，要么全不选。因此第二个sigma只与$ti$的质因数种类数有关。设 $g[ti]$ 表示 $ti$ 的质因数种类数，则

$$f(d)=\sum_{ti=1}^{\lfloor \frac{n}{d^2} \rfloor}2^{g[ti]}$$

  我们只需预处理 $g$ 数组即可。
  时间复杂度主要在预处理上，所以是 $O(n)$。（注意那个$\lfloor \frac{n}{d^2} \rfloor$，由于分母以平方速度增长，所以整个分数下降速度是很快的）

【100%】$n \le 10^{11}$

  上述解法的瓶颈在于$g[ti]$不好求，因为$ti$最大会达到$n$，预处理存不下，现场求又慢。所以对于$f(d)$我们要换一种求法。
  事实上，求$f(d)$是Mobius反演的经典问题。

$$\begin{aligned} f(d)&=\sum_{i=1}^n\sum_{j|i}(\gcd(j,\frac{i}{j})==d) \\ &=\sum_{i=1}^n\sum_{j=1,\ ij \le n}^n(\gcd(i,j)==d) \end{aligned}$$

  令$m=\lfloor \frac{n}{d^2} \rfloor$，则上式

$$\begin{aligned} &=\sum_{i=1}^m\sum_{j=1,\ ij \le m}^m(\gcd(i,j)==1) \\ &=\sum_{D=1}^m\mu(D)\sum_{t=1}^{\lfloor \frac{m}{D^2} \rfloor}\lfloor \frac{m}{D^2t} \rfloor \end{aligned}$$

  总式为

$$\sum_{d=1}^{\sqrt n}d*\sum_{D=1}^{\lfloor \frac{n}{d^2} \rfloor}\mu(D)\sum_{t=1}^{\lfloor \frac{n}{d^2D^2} \rfloor}\lfloor \frac{n}{d^2D^2t} \rfloor$$

  接下来用《莫比乌斯反演（宋新波）》里的一种变形。（参考wc2016课件）
  令$T=d*D$，则原式为

$$\sum_{T=1}^n\sum_{d|T}d*\mu(\frac{T}{d})\sum_{t=1}^{\lfloor \frac{n}{T^2} \rfloor}\lfloor \frac{n}{T^2t} \rfloor$$

  事实上如果$T>\sqrt n$，则第三个sigma无意义。所以原式为

$$\sum_{T=1}^{\sqrt n}G(T)\sum_{t=1}^{\lfloor \frac{n}{T^2} \rfloor}\lfloor \frac{n}{T^2t} \rfloor，其中G(T)=\sum_{d|T}d*\mu(\frac{T}{d})$$

  显然 $G$ 数组是可预处理的，第二个sigma可以分块解决。
  时间复杂度：预处理为 $O(\sqrt n \cdot \log(\sqrt n))$，最终式子求值为 $O(\sqrt n*?)$，$?$为一个不是很大的常数。（注意那个$\lfloor \frac{n}{T^2} \rfloor$，由于分母以平方速度增长，所以整个分数下降速度是很快的）