ngtkana https://blog.hatena.ne.jp/ngtkana/ ブログ名 https://blog.ngtkana.com/ ユークリッドの互除法 (Euclidean algorithm) といえば最小公倍数 (GCD) を計算するためのアルゴリズムですけれども、拡張することでモジュラー逆元、有理数復元などなど便利なことができることはみなさまご存知。ご存知…… アッ、じゃあこの記事いらないですね。 お疲れ様でした。 というわけで本文です。 1. 普通のユークリッドの互除法 (GCD の計算) まあこのへんはみなさまご存知でしょうし軽く流しましょう。 入力 正整数 $x \ge y > 0$ 出力 $\mathrm{gcd}(x, y)$ アルゴリズム 数列 $\left( r _ i \right) _ { i =… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2026%2F08%2F08%2F001812" title="ユークリッドの互除法を、めっちゃ解説します！ 拡張ユークリッド、有理数復元などです - ブログ名" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/n/ngtkana/20260807/20260807230134.png Hatena Blog https://hatena.blog 2026-08-08 00:18:12 rich https://blog.ngtkana.com/entry/2026/08/08/001812 1.0 100%