베개-CPU

현재 값이 $n$일 때, 과정이 끝날 때까지 걸리는 시간의 기댓값을 $f(n)$이라 하자. $f(1)=0$이다.

$n>1$에서 $2,3,\cdots,n$ 중 $n$의 약수인 수를 골랐을 때에만 값이 작아진다. $n$의 양의 약수 개수를 $\tau(n)$이라 하면, $2$ 이상인 약수는 $\tau(n)-1$개이다.

현재 상태에서 한 번의 선택을 수행한 뒤의 기댓값을 그대로 식으로 쓰면

$$\begin{aligned} f(n) &=1+\frac{n-\tau(n)}{n-1}f(n) +\frac{1}{n-1}\sum_{\substack{x\mid n\\x\ge 2}} f(n/x). \end{aligned}$$

$x$가 $2$ 이상인 $n$의 약수를 모두 돌 때 $n/x$는 $n$의 모든 진약수를 정확히 한 번씩 돈다. 따라서 식을 정리하면

$$f(n)=\frac{n-1+\displaystyle\sum_{\substack{d\mid n\\d<n}}f(d)}{\tau(n)-1}.$$

오른쪽에는 항상 $n$보다 작은 값의 $f$만 등장하므로 $n=2,3,\cdots$ 순서로 계산할 수 있다.

이를 $O(M\log M)$에 전처리할 수 있다. 여기서 $M$은 모든 테스트 케이스의 $N$ 중 최댓값이다. 배열 $S_n$에 의 진약수 에 대한 의 합을, 배열 에 진약수의 개수를 저장한다. 을 계산한 직후 모든 에 과 을 각각 더하면 된다. 전체 갱신 횟수는

$$\sum_{n=1}^{M}\left\lfloor\frac{M}{n}\right\rfloor=O(M\log M)$$

이다.

각 테스트 케이스의 답은 전처리된 $f(N)$을 소수점 아래 둘째 자리까지 반올림해 출력하면 된다.

Solution written by GPT5.6