最大公約数とユークリッドの互除法
2つの整数を割り切る最大の整数を探します。大きい方を余りに置き換えても公約数は変わりません。
言語：Python / 計算量：O(log min(A,B)) 回程度の除算
前提：繰り返しを1周ずつ追う
考え方
- a=bq+r と書けるので、a,bの公約数はb,rも割り切ります。
- rが0になるまで繰り返します。
- 最小公倍数は a//gcd(a,b)*b（正整数の場合）。
具体例
gcd(18,12): (18,12)→(12,6)→(6,0)。答えは6です。
実装
from math import gcd
a,b=18,12
print(gcd(a,b))
print(a//gcd(a,b)*b)注意する条件
先にa*bを計算すると固定幅整数ではあふれることがあります。0を含む最小公倍数は別途定義を確認します。
確認問題
gcd(24,18) は？
解答と理由
6
24=18+6、18=6×3なので最大公約数は6。
実装課題
正整数 A B（各≤10^12）の最小公倍数を求める。
入力:
6 8
出力:
24参考実装
from math import gcd
a,b=map(int,input().split())
print(a//gcd(a,b)*b)