《アルゴリズムを学ぶ》16.約数列挙

# Overview
約数列挙（Divisor Enumeration） は、整数 N のすべての約数を求める基本的な数論アルゴリズム。
[1.約数列挙の基本](#1-約数列挙の基本)
[2.約数列挙の応用](#2-約数列挙の応用)
[3.典型問題を解いてみる](#3-典型問題を解いてみる)

# 1. 約数列挙の基本
### 約数の定義
整数 $N$ の 約数 とは、$N$ を割り切ることができる整数 のこと。

例：
$N=12$ の場合、約数は {1, 2, 3, 4, 6, 12}
$N=17$ の場合、約数は {1, 17}（素数）

### (1) すべての整数を試す方法（O(N）)
一番単純な方法は、1 から $N$ までのすべての数で割り切れるかを確認する方法。

```python
def divisors_naive(n):
    result = []
    for i in range(1, n + 1):
        if n % i == 0:
            result.append(i)
    return result

print(divisors_naive(12))  # 出力: [1, 2, 3, 4, 6, 12]
```
- 時間計算量は O(N)（すべての数を試すため）
- 小さな数には問題ないが、大きな N では非効率

### (2) √N まで調べる効率的な方法（O(√N）)
約数は対になって現れるため、$i$ について 1 から $\sqrt{N}$まで調べるだけで十分。

＜アルゴリズムの考え方＞
もし $i $が $N $の約数なら、$\frac{N}{i}$も約数
例：
$N=12$ の場合
$1$ は約数 → $\frac{12}{1} = 12$も約数
$2$ は約数 → $\frac{12}{2} = 6$も約数
$3$ は約数 → $\frac{12}{3} = 4$も約数
$\sqrt{12}  ≈ 3.46$ なので 1〜3 まで調べればよい

<実装>
```python
import math

def divisors_efficient(n):
    result = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            result.append(i)
            if i != n // i:  # 重複を防ぐ
                result.append(n // i)
    return sorted(result)

print(divisors_efficient(12))  # 出力: [1, 2, 3, 4, 6, 12]
```
- 時間計算量$ O(√N) （平方根までしか調べないため、高速）
- `i != n // i` の条件で、平方数の重複を防ぐ
- 約数はソートしておくと使いやすい


# 2. 約数列挙の応用
### (1) 約数の個数を求める
約数の個数を求める場合、上記の `divisors_efficient()` の `len(result)` を取るだけで OK。

```python
def count_divisors(n):
    count = 0
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            count += 1
            if i != n // i:
                count += 1
    return count

print(count_divisors(12))  # 出力: 6（約数の個数）
```

### (2) 約数の総和を求める
```python
def sum_of_divisors(n):
    total = 0
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            total += i
            if i != n // i:
                total += n // i
    return total

print(sum_of_divisors(12))  # 出力: 28（1+2+3+4+6+12）
```

# 3. 典型問題を解いてみる

### 例題1. 約数列挙
**問題: N のすべての約数を求めよ。**
> [参考： ABC315 B - Find Divisors](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
import math

N = int(input())
result = []
for i in range(1, int(math.sqrt(N)) + 1):
    if N % i == 0:
        result.append(i)
        if i != N // i:
            result.append(N // i)
print(*sorted(result))
```
</details>

### 例題2. 約数の個数を求める
**問題: N の約数の個数を求めよ。**
> [参考： ABC318 B - Count Divisors](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
import math

N = int(input())
count = 0
for i in range(1, int(math.sqrt(N)) + 1):
    if N % i == 0:
        count += 1
        if i != N // i:
            count += 1
print(count)
```
</details>

### 例題3. 約数の総和を求める
**問題: N の約数の総和を求めよ。**
> [参考： ABC319 C - Sum of Divisors](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
import math

N = int(input())
total = 0
for i in range(1, int(math.sqrt(N)) + 1):
    if N % i == 0:
        total += i
        if i != N // i:
            total += N // i
print(total)
```
</details>

### 例題4. K 番目の約数を求める
**問題: N の約数を昇順で列挙し、K 番目の約数を出力せよ。**
> [参考： ABC320 B - K-th Divisor](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
import math

N, K = map(int, input().split())
result = []
for i in range(1, int(math.sqrt(N)) + 1):
    if N % i == 0:
        result.append(i)
        if i != N // i:
            result.append(N // i)
result.sort()

print(result[K-1] if K <= len(result) else -1)
```
</details>