Overview
ユークリッドの互除法（Euclidean Algorithm） は、2つの整数の最大公約数（GCD: Greatest Common Divisor）を効率的に求めるアルゴリズム。
現存する最古のアルゴリズムの一つとも。紀元前300年ごろの古代ギリシャの数学者ユークリッドの著書に記述があり、ほぼ当時のままの形で使われ続けている。
1.ユークリッドの互除法の基本
2.GCDの応用
3.典型問題を解いてみる
1. ユークリッドの互除法の基本
(1) 基本的な考え方
通常、2つの数字の最大公約数は、2つの数を素因数分解し、共通する素数から最大公約数を求める。ただしこの方法だと2つの数1の値が大きいと計算が困難になる。
ユークリッドの互除法は、2つの整数 A, B の最大公約数 GCD(A, B) について、以下の性質を持つ、と考える。
$$GCD(A,B)=GCD(B,AmodB)$$
例: GCD(48, 18)
48 % 18 = 12 → GCD(18, 12)
18 % 12 = 6 → GCD(12, 6)
12 % 6 = 0 → GCD(6, 0) = 6
B が 0 になった時の A(上記の例だと6) が最大公約数。
(2)基本実装
- 再帰版
def gcd_recursive(a, b):
if b == 0:
return a
return gcd_recursive(b, a % b)
- 反復版
def gcd_iterative(a, b):
while b:
a, b = b, a % b
return a
- 再帰版はシンプルだが、深い再帰でスタックオーバーフローのリスクがある
- 反復版はメモリ効率が良く、競技プログラミングでは推奨される
2. GCD の応用
(1) LCM（最小公倍数）の求め方
GCD を利用すると、LCM（Least Common Multiple: 最小公倍数）を求められる
$$LCM(A,B)= \frac{A×B}{GCD(A,B)}$$
LCM の実装
def lcm(a, b):
return (a * b) // gcd_iterative(a, b)
- 乗算後に GCD で割ると、最小公倍数が求められる
- GCD を使うことで、効率的に LCM を計算できる
(2) N 個の数の GCD / LCM
① N 個の数の GCD
from functools import reduce
def gcd_multiple(numbers):
return reduce(gcd_iterative, numbers)
numbers = [48, 18, 30]
print(gcd_multiple(numbers)) # 出力: 6
② N 個の数の LCM
def lcm_multiple(numbers):
return reduce(lambda x, y: lcm(x, y), numbers)
print(lcm_multiple(numbers)) # 出力: 720
- reduce() を使うと、N 個の GCD / LCM を求められる
- リストの全要素に対して GCD / LCM を適用
3. 典型問題を解いてみる
例題1. GCD を求める
問題: N 個の整数 A が与えられる。その最大公約数を求めよ。
回答
from functools import reduce
import math
N = int(input())
A = list(map(int, input().split()))
print(reduce(math.gcd, A))
例題2. 2つの整数の LCM を求める
問題: 2つの整数 A, B の最小公倍数を求めよ。
回答
import math
A, B = map(int, input().split())
print(A * B // math.gcd(A, B))
例題3. N 個の数の最小公倍数
問題: N 個の整数 A の最小公倍数を求めよ。
回答
from functools import reduce
import math
N = int(input())
A = list(map(int, input().split()))
def lcm(a, b):
return a * b // math.gcd(a, b)
print(reduce(lcm, A))
例題4. 互いに素であるペアをカウント
問題: N 個の整数 A の中から、互いに素なペア (i, j) の個数を求めよ。
回答
import math
N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N):
for j in range(i + 1, N):
if math.gcd(A[i], A[j]) == 1:
count += 1
print(count)
例題5. ある条件を満たす最小の数を求める
問題: N 個の整数 A について、全ての A[i] で割り切れる最小の X を求めよ。
回答
from functools import reduce
import math
N = int(input())
A = list(map(int, input().split()))
def lcm(a, b):
return a * b // math.gcd(a, b)
print(reduce(lcm, A))