Pillow CPU

Let $f(n)$ be the expected remaining time when the current value is $n$. We have $f(1)=0$.

For $n>1$, the value decreases only when the chosen integer is a divisor of $n$. If $\tau(n)$ is the number of positive divisors of $n$, then there are $\tau(n)-1$ valid choices among $2,3,\cdots,n$.

Writing the expectation after one choice gives

$$\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}$$

As $x$ ranges over the divisors of $n$ that are at least $2$, $n/x$ ranges over every proper divisor of $n$ exactly once. Rearranging yields

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

Only values $f(d)$ with $d<n$ appear on the right-hand side, so we may compute the values in increasing order of $n$.

Let $M$ be the maximum input value over all test cases. We can preprocess all answers in $O(M\log M)$. Store in $S_n$ the sum of $f(d)$ over proper divisors of , and in the number of proper divisors. Immediately after computing , add and to the corresponding arrays for every multiple . The total number of such updates is

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

For each test case, print the precomputed value $f(N)$ rounded to two digits after the decimal point.

Solution written by GPT5.6