P5856 "SWTR-3" Game

Little E is playing a number game.

Little E has $n$ positive integers $a_1,a_2,\dots,a_n$. He can perform the following operation any number of times: Choose a number $q$ and a set $S=\{d_1,d_2,\dots,d_m\}$ such that $a_{d_1},a_{d_2},\dots,a_{d_m}$ are divisible by $q$, and divide $a_{d_1},a_{d_2},\dots,a_{d_m}$ by $q$. - $q$ must be in the form $p^z$, where $p$ is a prime number and $z$ is a positive integer. Find the minimum number of operations needed to make all these numbers equal.

The first line contains an integer $n$. The second line contains $n$ integers $a_1,a_2,\dots,a_n$.

Output one integer representing the answer.

#### "Sample 1 Explanation" The initial sequence is 12 30 48 36 18. Choose $S=\{4,5\},p=3$, after the operation it becomes 12 30 48 12 6. Choose $S=\{1,3,4\},p=2$, after the operation it becomes 6 30 24 6 6. Choose $S=\{2\},p=5$, after the operation it becomes 6 6 24 6 6. Choose $S=\{3\},p=2^2=4$, after the operation it becomes 6 6 6 6 6. A total of 4 operations are used, and the method is not unique. #### "Constraints and Notes" **This problem uses bundled testdata.** Subtask ID | $n\leq$ | $a_i\leq$ | Special Property | Score :-: | :-: | :-: | :-: | :-: $1$ | $8$ | $50$ | There is a number equal to $1$ among $a_i$ | $13$ $2$ | $10$ | $100$ | None | $17$ $3$ | $10^3$ | $10^4$ | None | $29$ $4$ | $10^5$ | $10^6$ | None | $41$ For $100\%$ of the data, $1\leq n\leq 10^5$ and $1\leq a_i\leq 10^6$. For all test points, the time limit is 1s and the memory limit is 128MB. #### "Source" [Sweet Round 03 B](https://www.luogu.com.cn/contest/24755)。 idea & solution: ET2006 & Alex_Wei。 Translated by ChatGPT 5