No.2829 GCD Divination
タグ : / 解いたユーザー数 67
作問者 :
twitteryou
/ テスター :
👑 
p-adic
Problem Statement
You are given an integer $N$. Repeat the following action until $N$ becomes $1$.
・Choose an integer $M$ between $1$ and $N$, inclusive, uniformly at random. Replace $N$ with $\ \gcd (N,M)\ $.
Find the expected number of actions until $N$ becomes $1$.
Input
$N$
・$2 \leq N \leq 10^7$
・$N$ is an integer.
Output
Output the expected number of actions. The answer may be a non-integer. Your answer is judged as correct if either its absolute error or its relative error, compared with the reference solution's output (which is computed so that its error from the true value is at most $10^{-10}$), is at most $10^{-5}$.
Sample
Sample 1
Input
2
Output
2
In each trial, $1$ comes up with probability $\frac{1}{2}$, giving $\gcd(1,2)=1\ $, and the process ends. The value to find is $\sum_{i=1}^{\infty}i2^{-i}$. This equals $2$.
Sample 2
Input
3
Output
1.5
Sample 3
Input
4
Output
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。