P5589 Peppa Pig Plays a Game

Peppa and George are playing a game. Peppa writes the numbers $\{1,2,\cdots,n\}$ on the blackboard. Each round, they will choose a number $x$ that is currently on the blackboard uniformly at random, and then delete all positive integer powers of $x$. Formally, given the sequence $\{1,2,\cdots,n\}$, each time they uniformly select $1$ number $x$ that exists in the sequence, and delete all numbers of the form $\{x^k,k \in Z^{+}\}$. They played for a whole afternoon, but the game still did not end, so they want to know: after how many rounds is the game expected to end. If the absolute error between your answer and the correct answer is within $10^{-4}$, then it will be judged as correct.

The first line contains $1$ positive integer $t$, meaning Peppa and George plan to play $t$ games. Then follow $t$ lines, each with $1$ positive integer $n$, meaning Peppa wrote the numbers $\{1,2,\cdots,n\}$ on the blackboard and will start the game.

Output a total of $t$ lines, each containing $1$ decimal number, representing the answer. Keep the decimals. If the absolute error between your answer and the correct answer is within $10^{-4}$, then it will be judged as correct.

For $n=4$, If the deletion order is $\{1,2,3\},\{3,2,1\}$, then the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{1}=\frac{1}{12}$. If the deletion order is $\{1,3,2\},\{3,1,2\}$, then the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2}=\frac{1}{24}$. If the deletion order is $\{2,1,3\},\{2,3,1\}$, then the probability is $\frac{1}{4} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{8}$. For the remaining $12$ sequences that delete $4$ times, the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{24}$. It is easy to see that the answer is $\frac{2 \times 3}{12} + \frac{2 \times 3}{24}+\frac{2 \times 3}{8} + \frac{12 \times 4}{24}=\frac{7}{2}=3.50000$. ### Constraints For $20\%$ of the testdata, $n \leq 10$. For $60\%$ of the testdata, $n \leq 10^5$. For $100\%$ of the testdata, $n \leq 10^9,t \leq 100$. ### A Friendly Reminder from the Problem Setter For C++ users, for positive integers $n,k$, if you want to compute $\sqrt[k] n$, please try not to use the built-in C++ function $\operatorname{pow}$, in order to avoid possible unnecessary precision errors. # Input Format The first line contains $1$ positive integer $t$, meaning Peppa and George plan to play $t$ games. Then follow $t$ lines, each with $1$ positive integer $n$, meaning Peppa wrote the numbers $\{1,2,\cdots,n\}$ on the blackboard and will start the game. # Output Format Output a total of $t$ lines, each containing $1$ decimal number, representing the answer. Keep the decimals. If the absolute error between your answer and the correct answer is within $10^{-4}$, then it will be judged as correct. # Hint For $n=4$, If the deletion order is $\{1,2,3\},\{3,2,1\}$, then the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{1}=\frac{1}{12}$. If the deletion order is $\{1,3,2\},\{3,1,2\}$, then the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2}=\frac{1}{24}$. If the deletion order is $\{2,1,3\},\{2,3,1\}$, then the probability is $\frac{1}{4} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{8}$. For the remaining $12$ sequences that delete $4$ times, the probability is $\frac{1}{4} \times \frac{1}{3} \times \frac{1}{2} \times \frac{1}{1}=\frac{1}{24}$. It is easy to see that the answer is $\frac{2 \times 3}{12} + \frac{2 \times 3}{24}+\frac{2 \times 3}{8} + \frac{12 \times 4}{24}=\frac{7}{2}=3.50000$ Translated by ChatGPT 5