约数链

将满足条件的 $S(n)$ 的非空子集称为 因数链。

对于正整数 $m$，定义 $g(m)$ 为最大元素恰好为 $m$ 的因数链数量。此链中的所有元素都是 $m$ 的因数。

移除最大元素 $m$ 后，剩余部分要么为空集，要么是一条最大元素为 $m$ 的真因数 $d$ 的因数链。反之，向任一这样的链添加 $m$，都会得到最大元素为 $m$ 的合法链。因此，

$$g(m)=1+\sum_{\substack{d\mid m\\d<m}}g(d)$$

其中最前面的 $1$ 对应只包含 $m$ 的单元素链。

从 $S(n)$ 选择的每条因数链都存在唯一的最大元素 $d$，且 $d\mid n$，因此

$$f(n)=\sum_{d\mid n}g(d)$$

按顺序计算 $g(1),g(2),\cdots,g(N)$。首先把所有 $g(m)$ 初始化为 $1$。当 已经确定时，把它加到 的每个真倍数 对应的 上。由于 ，处理 时所有真因数的贡献都已计入。

根据递推式，$\sum_{d\mid n,d<n}g(d)=g(n)-1$，所以

$$f(n)=2g(n)-1$$

仿照埃拉托斯特尼筛法遍历倍数，总时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。当 $1\le n\le 100\,000$ 时，最大答案为 ，可以用有符号 位整数表示。

Solution written by GPT6