kyopro_friends https://blog.hatena.ne.jp/kyopro_friends/ kyopro_friends’ diary https://kyopro-friends.hatenablog.com/ スナネコです。拡張GCDについての質問に答えます。問題： 以下のように実装された extgcdがある。 整数 が を満たし、extgcd(a, b) の返り値を としたとき、 が成り立つことを示せ。 def extgcd(a, b): # ax+by=gcd(x,y) を満たす (x,y) を返す if b == 0: return (1, 0) X, Y = extgcd(b, a % b) x = Y y = X - a // b * Y return (x, y) extgcd(a, b) が「 を満たす整数 を返すこと」の証明は省略します。最初に補題を示しておきます。 補題★： 0 で… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkyopro-friends.hatenablog.com%2Fentry%2F2024%2F03%2F18%2F192821" title="拡張GCDについて - kyopro_friends’ 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 2024-03-18 19:28:21 rich https://kyopro-friends.hatenablog.com/entry/2024/03/18/192821 1.0 100%