31757번 - Greek Casino 스페셜 저지다국어

문제

Since the early civilizations, humankind has enjoyed games of chance. Even the ingenious Greeks, known for their groundbreaking concept of the least common multiple (LCM), couldn’t resist a good gamble.

Inspired by this mathematical marvel, folks in Athens devised a unique betting system: after purchasing a ticket, a participant would receive a random number of coins. To determine this number, there are $N ≥ 3$ ordered slots numbered from 1ドル$ to $N$. A token is initially placed at slot 1ドル,ドル and the following steps are repeated:

• Let $xv be the number of the slot where the token is currently located.
• Generate a random integer $y$ between 1ドル$ and $N,ドル and compute $z$ the LCM of $x$ and $y$.
• If $z > N,ドル the procedure ends.
• Otherwise, the token is moved to slot $z,ドル and the participant receives one coin.

As it is well known, the house always wins: the casino employs a particular probability distribution for generating random integers, so as to ensure a profitable outcome.

The casino owner is constantly seeking to optimize the betting system’s profitability. You, an AI designed to aid in such tasks, are given $N$ and the probability distribution. Determine the expected total number of coins awarded to a participant.

입력

The first line contains an integer $N$ (3ドル ≤ N ≤ 10^5$) indicating the number of slots.

The second line contains $N$ integers $W_1, W_2, \dots , W_N$ (1ドル ≤ W_i ≤ 1000$ for $i = 1, 2, \dots , N$), representing that the probability of generating $i$ is $W_i/ \left( \sum_j{W_j} \right),ドル that is, the probability of generating $i$ is the relative weight of $W_i$ with respect to the sum of the whole list $W_1, W_2, \dots , W_N$.

출력

Output a single line with the expected total number of coins awarded to a participant. The output must have an absolute or relative error of at most 10ドル^{-9}$. It can be proven that the procedure described in the statement ends within a finite number of iterations with probability 1ドル,ドル and that the expected total number of coins is indeed finite.

제한

힌트