E - E and PI 解説 by hos_lyric
(より詳しい解説は後日ブログで公開します)
\(n \ge 2\) のときの様子を考えます.\(P_0\) から正の向きに回って最も近い点を \(P_x\),負の向きに回って最も近い点を \(P_y\) とし,\(P_0\) からそれらまでの弧の長さをそれぞれ \(l, r\) とします.このとき,\(n\) 個の弧の長さは以下のようになることが証明できます:
- 長さ \(l\) が \(n - x\) 個
- 長さ \(r\) が \(n - y\) 個
- 長さ \(l + r\) が \(x + y - n\) 個
\(x + y = n\) のとき \(f(n) = \max\{l, r\}\),そうでないとき \(x + y < n\) で \(f(n) = l + r\) です.
さらに \(n\) が増えていく様子を考えると,\(x, y\) や \(l, r\) は互除法のように変わっていくことがわかります.具体的には,\(n\) が \(x + y\) を超えると \(l > r\) のとき \(x := x + y\),\(l := l - r\),\(l < r\) のとき \(y := y + x\),\(r := r - l\) と変化します.このような変化が起こる \(n\) は問題文の \(n_k\) によって \(n = n_k + 2\) となります.\(n_k + 1\) が \(e\) の semiconvergent の分母であると見ることもできます (https://oeis.org/A119015).
\(e\) の連分数展開は \([2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, \ldots]\) となることが知られているので,必要な互除法を \(O(\sqrt{K})\) 時間で実行できます.
投稿日時:
最終更新: