题目大意

有函数 $S(n)$ 定义如下：

这里序列 $\{d_i\}$ 是正整数 $n \in [1,2\times 10^6]$ 的所有真约数（去重）的升序排列，求 $\sum_{i=1}^n S(i)$

思路

我们先用样例 $n=6$ 打表看看有什么规律：

我们发现，其求和可以变成，

不难发现对于某个因子 $d$ 对于整体的贡献，就是其对于某个数 $x\in[1,n]$ 的升序排序的次序。例如因子 $2$ ，其整除的数有 $\{2,4,6\}$ 在这三个数的因子排序都是第2个，所以其贡献是 $-2^2\times 3$。

那么我们可以根据这个发现，先枚举 $[1,n]$ 的所有因子 $d$ ，然后枚举其倍数 $\{d,2d,3d,\cdots | xd \le n\}$ ，作一个计数器用于记录其出现的次数，然后根据其出现的次数作贡献即可。

即使用埃氏筛的思想，枚举倍数

[!NOTE]

这里还可以思考下是否存在 $O(n)$ 的线筛做法，我的思路是把每个数作质因数分解，看看是否存在递推（或者化归） $S(n)=S(p_1)S(p_2)\cdots S(p_k)$ 或者 $S(n)=aS(p_1)+bS(p_2)\cdots +cS(p_k)$ 的性质，然后就可以预处理质因数的 $S(n)$ 然后递推了。

但是我代几个数发现似乎并不存在这样的性质，所以这里就不展开了。

代码

这里外循环 $n$ 次，然后内循环每个 $i$ 执行 $\lfloor \frac{n}{i} \rfloor$ 次 ，总的次数是，

即时间复杂度是 $O(n\log n)$ 在2e6下还是可以过的

最后

我们知道了枚举倍数的筛思想，下面引出埃氏筛（筛质数）：

埃氏筛是一种用于筛选质数的算法，其思路是：如果一个数 $n$ 是质数，那么它的倍数 $2n,3n,4n,\cdots$ 一定不是质数。因此，我们可以从 $2$ 开始，依次标记每个质数的倍数，最后剩下的数就是质数。

由于埃氏筛只对质数进行倍数枚举，其时间复杂度是 $O(n\log \log n)$

[!TIP]

类似的题目:

• [GESP202509 五级] 数字选取 筛质数模板题（大雾
• Bitwise Or vs LCM 这里要点放缩的小巧思
• [Brooklyn Round 1 & NNOI Round 1 A] Flying Flower 找到最优策略就好