동작 원리

이 장에서는 작은 수로 각 알고리즘을 한 단계씩 추적합니다. 표의 숫자를 직접 따라 계산해 보면 코드가 왜 그렇게 생겼는지 자연스럽게 이해됩니다.

유클리드 호제법: gcd(252, 105)

a를 b로 나눈 나머지를 r이라고 하면 a와 b의 공약수는 b와 r의 공약수와 정확히 같습니다(r = a - q × b이므로). 그래서 (a, b)를 (b, r)로 바꿔도 GCD는 변하지 않고, 수는 계속 작아집니다.

나머지가 0이 된 3단계의 b = 21이 답입니다. 단 3번 만에 끝났습니다.

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

print(gcd(252, 105))  # 21

확장 유클리드 호제법: 240x + 46y = gcd(240, 46)

확장 버전은 나머지 r과 함께, 그 r을 240 × x + 46 × y 꼴로 만드는 계수 x, y를 같이 갱신합니다. 몫 q가 나올 때마다 세 값 모두 새 값 = 이전 값 - q × 현재 값 규칙을 따릅니다.

나머지가 0이 되기 직전 줄이 답입니다. gcd = 2, x = -9, y = 47이고, 실제로 240 × (-9) + 46 × 47 = -2160 + 2162 = 2입니다. 모든 줄에서 240 × x + 46 × y = r이 성립한다는 점을 확인해 보세요. 이 불변식이 알고리즘이 맞는 이유입니다.

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    old_r, r = a, b
    old_x, x = 1, 0
    old_y, y = 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y
    return old_r, old_x, old_y

print(extended_gcd(240, 46))  # (2, -9, 47)

빠른 거듭제곱: 3^13 mod 7

3^13을 곱셈 12번으로 구하는 대신 지수를 이진수로 봅니다. 13 = 1101(2) = 8 + 4 + 1이므로 3^13 = 3^8 × 3^4 × 3^1입니다. 밑을 계속 제곱하면서(3, 3^2, 3^4, 3^8 …) 지수의 비트가 1인 자리만 결과에 곱합니다.

답은 3입니다. 페르마의 소정리로 확인할 수도 있습니다. 3^6 ≡ 1 (mod 7)이므로 3^13 = (3^6)^2 × 3 ≡ 3입니다. 곱셈 횟수는 지수의 비트 수에 비례하므로 지수가 10^18이어도 약 60번의 반복이면 끝납니다.

에라토스테네스의 체: 30 이하의 소수

2부터 시작해서, 아직 지워지지 않은 수를 만나면 그 수는 소수이고 그 배수를 모두 지웁니다. 배수는 i × i부터 지우면 충분합니다. 그보다 작은 배수 i × k(k < i)는 이미 더 작은 소인수 k 단계에서 지워졌기 때문입니다.

남은 수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29로 모두 10개입니다. i × i ≤ n인 동안만 바깥 반복을 돌면 되므로, 30의 경우 i = 5에서 사실상 일이 끝납니다.

소인수분해와 nCr mod p

소인수분해의 가장 단순한 방법은 2부터 √n까지 나누어 보는 것입니다. 360이라면 2로 세 번(360 → 180 → 90 → 45), 3으로 두 번(45 → 15 → 5) 나누고, 남은 5는 √5보다 작은 약수가 없으므로 소수입니다. 따라서 360 = 2^3 × 3^2 × 5입니다.

이항 계수 C(n, r) = n! / (r! × (n - r)!)을 소수 p로 나눈 나머지는 나눗셈이 있어서 바로 계산할 수 없습니다. 대신 분모의 역원을 곱합니다. 분모를 페르마의 소정리로 뒤집으면 C(n, r) ≡ n! × (r!)^(p-2) × ((n-r)!)^(p-2) (mod p)입니다(n이 p보다 작을 때).

p = 10**9 + 7

def ncr_mod(n: int, r: int) -> int:
    if r < 0 or r > n:
        return 0
    num = den = 1
    for i in range(r):
        num = num * (n - i) % p
        den = den * (i + 1) % p
    return num * pow(den, p - 2, p) % p

print(ncr_mod(10, 3))       # 120
print(ncr_mod(100000, 50000))  # 149033233 — 정확한 값은 3만 자리가 넘지만 나머지는 금방 나옵니다

정리

유클리드 호제법은 큰 수를 나머지로 바꿔 빠르게 줄이고, 확장 버전은 그 과정에서 베주 계수를 함께 따라갑니다. 빠른 거듭제곱은 지수의 이진 표현을 이용해 곱셈 횟수를 로그 수준으로 줄입니다. 체는 소수의 배수를 i × i부터 지워 범위 안의 소수를 한 번에 찾고, nCr mod p는 나눗셈 대신 역원을 곱합니다. 다음 장에서는 이 내용을 재사용할 수 있는 코드로 정리합니다.