inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ https://atcoder.jp/contests/abc333/tasks/abc333_g分母がN以下で実数rに最も近い分数を最良近似と言います。これは連分数と結びついています。 例えば、0.45を連分数で表すと、 となります。これは次のように求められます。 の逆数を取るとで、この整数部分は2で、小数部分は、この逆数はで、整数部分は4で、小数部分は、この逆数は2なので、整数部分は2です。 この3つの整数部分、2, 4, 2を並べると連分数になります。 さて、この連分数を途中で打ち切ると、最良近似になります。計算してみると、となります。この計算は、整数部分を、とすると、 としたとき、が最… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F2023%2F12%2F20%2F200532" title="AtCoder Beginner Contest 333 G - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2023-12-20 20:05:32 rich https://inamori.hateblo.jp/entry/2023/12/20/200532 1.0 100%