No.2829 GCD Divination

問題提出提出一覧質問統計解説

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が

10^{-5}

以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 61
作問者 :

ねしん / テスター : 👑

p-adic

3 ProblemId : 11030 / 出題時の順位表 / 自分の提出

問題文最終更新日: 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}$ 以下の場合正解になります。

試行ごとに $\frac{1}{2}$ で $1$ が出て、 $\gcd(1,2)=1\$ となり終わります。求める値は $\sum_{i=1}^{\infty}i2^{-i}$ となります。これは $2$ です。

1.5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。