qnighy https://blog.hatena.ne.jp/qnighy/ 簡潔なQ https://qnighy.hatenablog.com/ Programming Algorithm ユークリッドの互除法を考える。 数a,bが与えられる。 1. 最初はx=a, y=bとする。 2. xをyで割った余りにする。 3. yをxで割った余りにする。 4. 2に戻る。 5. xかyが0になったときに、もう一方が最大公約数である。 ここで、この数x,yを、別の方法で表現することを考える。つまり x = a * x' + b * x'' y = a * y' + b * y''まず、最初の初期化では次のようになる。 x = a * 1 + b * 0 = a y = a * 0 + b * 1 = bまた、この形式を保持しながら、「余り」の計算を行うことが可能である。 xをyで割った余… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fqnighy.hatenablog.com%2Fentry%2F20091230%2F1262173513" title="超わかりやすい拡張ユークリッドの互除法 - 簡潔なQ" 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 2009-12-30 20:45:13 rich https://qnighy.hatenablog.com/entry/20091230/1262173513 1.0 100%