ユークリッドの互除法
参考：https://qiita.com/drken/items/b97ff231e43bce50199a
1. ユークリッドの互除法
最大公約数を求めるアルゴリズム
最大公約数を求めたいだけなら，math.gcd(a, b) を使おう．
code: python
def euclid(a: int, b: int):
if b == 0: return a
else: return euclid(b, a % b)
# 使用例
print(euclid(24, 12)) # 出力：12
print(euclid(32, 12)) # 出力：4
再帰を使わない版
code: python
def euclid(a: int, b: int):
while b > 0:
a, b = b, a % b
return a
# 使用例
print(euclid(24, 12)) # 出力：12
print(euclid(32, 12)) # 出力：4
2. 拡張ユークリッドの互除法
一次不定方程式 $ ax+by={\rm gcd}(a, b)を満たす$ x, yを求めるアルゴリズム
code: python
def ex_euclid(a: int, b: int):
if b == 0:
return a, 1, 0
g, x, y = ex_euclid(b, a % b)
return g, x, y - (a // b) * t
# 使用例
print(ex_euclid(24, 12)) # 出力：(12, 0, 1) 24 * 0 + 12 * 1 = 12
print(ex_euclid(32, 12)) # 出力：(4, -1, 3) 32 * (-1) + 12 * 3 = 4
再帰を使わない版　（参考：https://qiita.com/akebono-san/items/f00c0db99342a8d68e5d）
code: python
def ex_euclid(a: int, b: int):
x, y, u, v = 1, 0, 0, 1
while b > 0:
x, y, u, v = u, v, x - (a // b) * u, y - (a // b) * v
a, b = b, a % b
return a, x, y
# 使用例
print(ex_euclid(24, 12)) # 出力：(12, 0, 1) 24 * 0 + 12 * 1 = 12
print(ex_euclid(32, 12)) # 出力：(4, -1, 3) 32 * (-1) + 12 * 3 = 4
#数学 #約数 #倍数 #ユークリッドの互除法