No.2829 GCD Divination
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$10^{-5}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 56
作問者 :
ねしん
/ テスター :
👑 
p-adic
タグ : / 解いたユーザー数 56
作問者 :
ねしん
/ テスター :
👑 p-adic
問題文最終更新日: 2024-08-04 08:20:12
問題文
整数$N$が渡されます。次の行動を$N$が$1$になるまで繰り返していきます。
・$1$以上$N$以下の整数$M$を等確率でランダムに選ぶ。$N$を$\ \gcd (N,M)\ $で置き換える。
$N$が$1$になるまでかかる回数の期待値を求めてください。
入力
$N$
・$2 \leq N \leq 10^7$
・$N$は整数
出力
回数の期待値を出力してください。答えは小数になることがあります。真の値との誤差が$10^{-10}$以下となるように作成された想定解との絶対誤差もしくは相対誤差のどちらかが$10^{-5}$以下の場合正解になります。
サンプル
サンプル1
入力
2
出力
2
試行ごとに$\frac{1}{2}$で$1$が出て、$\gcd(1,2)=1\ $となり終わります。求める値は$\sum_{i=1}^{\infty}i2^{-i}$となります。これは$2$です。
サンプル2
入力
3
出力
1.5
サンプル3
入力
4
出力
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。