약수 체인

집합 $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$를 가지며, $d\mid n$이므로

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

이다.

$g(1),g(2),\cdots,g(N)$을 순서대로 계산한다. 처음 모든 $g(m)$을 $1$로 초기화하고, 가 확정될 때마다 의 모든 진배수 에 를 더한다. 이므로 를 처리하는 시점에는 이미 모든 진약수의 기여가 반영되어 있다.

마지막으로 $f(n)$은 $g(n)$과 같은 시점에 계산할 수 있다. 점화식에서 $\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