約数チェーン

$S(n)$ の条件を満たす空でない部分集合を 約数チェーン と呼ぶ。

正の整数 $m$ について、最大要素がちょうど $m$ である約数チェーンの個数を $g(m)$ とする。そのチェーンのすべての要素は $m$ の約数である。

最大要素 $m$ を除くと、空集合になるか、最大要素が $m$ の真の約数 $d$ である約数チェーンになる。逆に、そのようなチェーンへ $m$ を追加すると最大要素が $m$ のチェーンが得られる。よって

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

である。最初の $1$ は要素が $m$ だけのチェーンを表す。

$S(n)$ から選ぶ約数チェーンには最大要素 $d$ がただ1つ存在し、$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