Python3.0による拡張ユークリッドの互除法

Python
1# 拡張ユークリッドの互除法
2# input: 二つの整数a, b
3# output: d=gcd(a, b)とax+by = dを満たす整数x, y
4def ex_euclid(a, b):
5    if abs(a) < abs(b): # a, bの絶対値を比較(abs(a) = |a|, abs(b) = |b|)
6        a, b = b, a     # |a| < |b| の場合は, a(割られる数)とb(割る数)を入れ替える
7        change_flag = 1 # a, bの入れ替えがある場合とない場合とで、出力が変わるので、入れ替えがあったかどうかを記録
8    else:
9        change_flag = 0 # a, bの入れ替えがある場合とない場合とで、出力が変わるので、入れ替えがあったかどうかを記録
10
11    a0, a1 = a, b
12    x0, x1 = 1, 0
13    y0, y1 = 0, 1
14    while True:
15        if a1 == 0:
16            if change_flag == 0:
17                return [a0, x0, y0] # a, bの入れ替えがない場合はそのまま出力
18            else:
19                return [a0, y0, x0] # a, bを入れ替えた場合はy0, x0を入れ替えて出力
20
21        # 以下の "=" の後にコードを書いて関数を完成させてください。
22        # qはa0をa1で割った時の商で, rはその時の剰余です。
23        r = mod(a0, a1)
24        q = (a0-r)//a1
25        x0, x1 = 
26        y0, y1 =
27        a0, a1 =

行動規範の内容に同意します

回答1件

python
1def gcd_ext(a, b):
2    """
3    # 拡張ユークリッドの互除法
4    # a*x + b*y = gcd(a,b) となる (x,y) を求める.
5    http://www.tbasic.org/reference/old/ExEuclid.html
6    """
7    x, y, lastx, lasty = 0, 1, 1, 0
8    while b != 0:
9        q = a // b
10        a, b = b, a % b
11        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
12    return (lastx, lasty)