《アルゴリズムを学ぶ》15.ユークリッドの互除法

# Overview
ユークリッドの互除法（Euclidean Algorithm） は、2つの整数の最大公約数（GCD: Greatest Common Divisor）を効率的に求めるアルゴリズム。

>現存する最古のアルゴリズムの一つとも。紀元前300年ごろの古代ギリシャの数学者ユークリッドの著書に記述があり、ほぼ当時のままの形で使われ続けている。

[1.ユークリッドの互除法の基本](#1-ユークリッドの互除法の基本)
[2.GCDの応用](#2-gcd-の応用)
[3.典型問題を解いてみる](#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)基本実装
- 再帰版
```python
def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)
```
<br>

- 反復版
```python
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 の実装
```python
def lcm(a, b):
    return (a * b) // gcd_iterative(a, b)
```
- 乗算後に GCD で割ると、最小公倍数が求められる
- GCD を使うことで、効率的に LCM を計算できる

### (2) N 個の数の GCD / LCM
##### ① N 個の数の GCD
```python
from functools import reduce

def gcd_multiple(numbers):
    return reduce(gcd_iterative, numbers)

numbers = [48, 18, 30]
print(gcd_multiple(numbers))  # 出力: 6
```

##### ② N 個の数の LCM
```python
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 が与えられる。その最大公約数を求めよ。**
> [参考： ABC315 B - Find GCD](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
from functools import reduce
import math

N = int(input())
A = list(map(int, input().split()))

print(reduce(math.gcd, A))
```
</details>

### 例題2. 2つの整数の LCM を求める
**問題: 2つの整数 A, B の最小公倍数を求めよ。**
> [参考： ABC318 B - Find LCM](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
import math

A, B = map(int, input().split())
print(A * B // math.gcd(A, B))
```
</details>

### 例題3. N 個の数の最小公倍数
**問題: N 個の整数 A の最小公倍数を求めよ。**
> [参考： ABC319 C - Find LCM Multiple](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
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))
```
</details>

### 例題4. 互いに素であるペアをカウント
**問題: N 個の整数 A の中から、互いに素なペア (i, j) の個数を求めよ。**
> [参考： ABC320 B - Count Coprime Pairs](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
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)
```
</details>

### 例題5. ある条件を満たす最小の数を求める
**問題: N 個の整数 A について、全ての A[i] で割り切れる最小の X を求めよ。**
> [参考： ABC322 C - Smallest Common Multiple](https://atcoder.jp/contests/abc322/tasks/abc322_c)
<details><summary> 回答　</summary>

```python
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))
```
</details>