수업 목표

본 수업은 알고리즘 해결과 암호학의 기반이 되는 정수론, 조합론, 선형대수학의 핵심 원리를 이해하고, 파이썬을 이용한 고속 모듈러 산술과 게임 이론 알고리즘을 설계할 수 있는 능력을 기르는 것을 목표로 합니다. - 분할 정복을 활용한 빠른 거듭제곱과 페르마의 소정리를 결합하여 지수가 극도로 큰 모듈러 거듭제곱을 최적화합니다. - 모듈러 역원을 $O(N)$에 전처리하여 여러 개의 이항 계수($\binom{n}{r}$) 쿼리를 $O(1)$에 즉시 해결하는 조합 기법을 습득합니다. - 피보나치 등 선형 점화식의 관계를 행렬식으로 변환하고 행렬 거듭제곱을 이용해 $O(\log N)$ 시간에 연산하는 기법을 구현합니다. - 스프라그-그룬디 정리(Sprague-Grundy Theorem)와 XOR 합(Nim-sum)의 수학적 대칭성을 규명하고 님 게임의 승패 판정에 적용합니다.

학습 동기부여

컴퓨터 알고리즘 설계와 보안 암호학(예: RSA 비대칭키 암호화)에서 수학적 원리의 적용은 병목을 해결하는 결정적 무기입니다. 예를 들어 10의 18승 단계의 피보나치 수를 일반 DP로 연산하면 인류의 일생을 다 바쳐도 끝나지 않지만, 행렬 거듭제곱 최적화를 적용하면 단 0.001초 만에 연산이 완료됩니다. 또한 포함배제, 조합론의 팩토리얼 역원 계산은 대규모 경우의 수를 다루는 핵심 도구입니다. 본 수업에서 다루는 모듈러 대수와 수학적 모델들은 계산의 한계를 뛰어넘어 초고속 고성능 시스템을 구축할 수 있게 돕습니다.

도입 스토리

두 사람이 돌 무더기들 앞에 앉아 번갈아 돌을 가져가는 고대의 보드 게임이 있습니다. 마지막 돌을 가져가는 자가 이기는 이 단순한 놀이는 얼핏 보면 상대방의 심리를 꿰뚫고 직관에 의존해야 이길 수 있을 것처럼 보입니다. 그러나 사실 모든 돌 무더기의 개수를 이진수로 변환하고 비트별로 더한 값(XOR 합)을 계산해 보면, 이 게임의 승패 결과는 게임을 시작하기도 전에 선공과 후공 중 누구에게 필승 경로가 있는지 수학적으로 완벽히 정해져 있습니다. 이처럼 복잡해 보이는 세계의 흐름을 단 몇 개의 비트 연산으로 규명해 내는 모듈러 대수와 조합 게임 이론의 강력함을 본 수업에서 파헤쳐 봅니다.

1. 수론 - 빠른 거듭제곱과 페르마의 소정리

분할 정복 기반의 거듭제곱은 $O(\log N)$에 $a^b \pmod m$을 구합니다. 소수 $p$에 대해 $a^{p-1} \equiv 1 \pmod p$가 성립한다는 페르마의 소정리를 이용하면 지수 부분이 또 다른 거듭제곱 형태인 $b^c$로 주어질 때 지수 자체에 모듈러 $p-1$을 법으로 먼저 적용함으로써 연산의 범위를 획기적으로 낮출 수 있습니다.

# 8057번: 빠른 거듭제곱 II — 지수에 p-1 모듈러를 적용한 고속 연산
import sys
input = sys.stdin.readline

def power(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

n = int(input())
p = 1000000007
for _ in range(n):
    a, b, c = map(int, input().split())
    # 페르마 소정리에 의해 지수부 b^c에 p-1 모듈러를 먼저 적용
    exp = power(b, c, p - 1)
    print(power(a, exp, p))

2. 조합론 - 이항 계수와 역원 전처리

조합의 수 $\binom{n}{r} = \frac{n!}{r!(n-r)!} \pmod p$를 여러 쿼리에 대해 빠르게 해결하려면 팩토리얼 수열과 그 역원을 미리 계산해야 합니다. 페르마 소정리에 의해 $x^{-1} \equiv x^{p-2} \pmod p$임을 사용하여 최대 크기 $N$의 역원 inv_fact[N]을 먼저 구한 뒤, 역순으로 inv_fact[i] = inv_fact[i+1] * (i+1) % p 공식을 적용하면 단 $O(N)$ 시간 안에 1부터 $N$까지의 모든 팩토리얼 역원을 구해두고 각 조합 질의를 $O(1)$에 해결할 수 있습니다.

# 8058번: 이항 계수 쿼리 — O(N) 전처리 후 O(1) 조합 합산
import sys
input = sys.stdin.readline

p = 1000000007
MAX = 1000000

# 팩토리얼 배열 전처리
fact = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    fact[i] = (fact[i - 1] * i) % p

# 페르마 소정리 역원 전처리
def power(base, exp):
    res = 1
    base %= p
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % p
        base = (base * base) % p
        exp //= 2
    return res

inv_fact = [1] * (MAX + 1)
inv_fact[MAX] = power(fact[MAX], p - 2)
# 역순 전파를 통해 O(N)에 전체 역원 테이블 구축
for i in range(MAX - 1, -1, -1):
    inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % p

n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    if b < 0 or b > a:
        print(0)
    else:
        ans = (fact[a] * inv_fact[b]) % p
        ans = (ans * inv_fact[a - b]) % p
        print(ans)

3. 행렬 거듭제곱과 피보나치 점화식

점화식 $F_n = F_{n-1} + F_{n-2}$의 항 전이를 선형대수의 행렬 곱셈 관계로 식을 정립하면 다음과 같이 변환할 수 있습니다: $\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} \implies \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_1 \\ F_0 \end{pmatrix}$ 따라서 $2 \times 2$ 기본 행렬을 분할 정복 거듭제곱 기법으로 빠르게 제곱하여 $O(\log N)$에 극도로 큰 인덱스의 피보나치 수를 오차 없이 모듈러 산술로 계산할 수 있습니다.

# 8059번: 피보나치 수열 — O(log N) 행렬 거듭제곱 최적화
import sys
input = sys.stdin.readline

def multiply(A, B, mod):
    C = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            s = 0
            for k in range(2):
                s = (s + A[i][k] * B[k][j]) % mod
            C[i][j] = s
    return C

def power_matrix(A, n, mod):
    res = [[1, 0], [0, 1]]
    base = A
    while n > 0:
        if n % 2 == 1:
            res = multiply(res, base, mod)
        base = multiply(base, base, mod)
        n //= 2
    return res

n = int(input())
if n == 0:
    print(0)
else:
    p = 1000000007
    T = [[1, 1], [1, 0]]
    # T^(n-1) 행렬의 [0][0] 번째 원소가 F_n에 대응됨
    res = power_matrix(T, n - 1, p)
    print(res[0][0])

4. 게임 이론 - 님 게임 (Nim Game)

님 게임은 각 플레이어가 번갈아가며 한 더미에서 돌을 임의로 제거하고 마지막 돌을 제거하는 사람이 승리하는 공평 게임(Impartial Game)입니다. - **스프라그-그룬디 정리**: 모든 더미의 돌 개수의 XOR 비트합 $S = x_1 \oplus x_2 \oplus \dots \oplus x_n$ (Nim-sum)을 구합니다. - $S \neq 0$인 경우 선공의 필승 상태(Winning State)입니다. 선공은 적절히 돌을 제거하여 XOR 합을 항상 $0$으로 만들어 후공을 패배 상태로 밀어 넣을 수 있습니다. - $S = 0$인 경우 후공의 필승 상태(Losing State)입니다. 선공이 어떤 돌을 가져가도 다음 상태의 XOR 합은 무조건 0이 아닌 값이 되므로 후공이 이를 다시 0으로 통제할 수 있습니다.

# 8060번: 님 게임 — XOR 비트 연산으로 O(N) 판정
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    x = list(map(int, input().split()))
    
    xor_sum = 0
    for num in x:
        xor_sum ^= num
        
    if xor_sum != 0:
        print("first")
    else:
        print("second")

자주 하는 실수 & 오류 예방

- 지수 모듈러의 오용: $a^{b^c} \pmod p$를 풀 때 지수 $b^c$에 동일한 모듈러 $p$를 적용하면 오답이 됩니다. 지수부에는 오일러의 정리 및 페르마의 소정리에 따라 반드시 $p-1$ (즉, $10^9+6$)을 모듈러로 적용하여 계산하십시오. - 음수 뺄셈 후 모듈러 보정: 모듈러 곱셈 역원을 이용하여 나눗셈 구간의 뺄셈 조합을 진행할 때, 뺄셈 연산 결과가 음수가 되는 것을 대비해 (A - B + p) % p 형태로 보정값을 취해야 파이썬 및 기타 언어에서 음수 모듈러에 의한 불규칙 에러를 원천 차단할 수 있습니다. - 피보나치 행렬 연산 $N=0$ 예외: $N=0$ 일 때 행렬 승수 연산 진입 시 $n-1 = -1$이 되어 루프 무한 루프나 인덱스 침범이 나지 않도록 함수의 초입부에 예외 필터링 조건을 두어야 합니다.

핵심 정리

알고리즘 및 정리	시간 복잡도	공간 복잡도	법(Modulo) 기준	주요 적용 주제
페르마 소정리 지수 감축	$O(\log c + \log \text{exp})$	$O(1)$	지수는 $p-1$, 밑은 $p$ 적용	다중 거듭제곱 탑 형태의 빠른 모듈러 연산
선형 팩토리얼 역원 전처리	$O(MAX)$ 전처리, 쿼리 $O(1)$	$O(MAX)$	소수 $p$	이항 계수 및 조합 경우의 수 쿼리 다량 처리
행렬 거듭제곱 (Matrix Exp)	$O(\log N)$ (상수 크기 행렬)	$O(1)$	소수 $p$	인덱스가 $10^{18}$에 달하는 점화식 수열 계산
그룬디 Nim-sum 판정	$O(N)$ (단일 스캔)	$O(1)$	비트 XOR 연산	공평 조합 게임의 필승 전략 선/후공 판정

실습 문제

문제 번호	문제 제목	출처	난이도	핵심 알고리즘
8057	빠른 거듭제곱 II	CSES	쉬움	페르마의 소정리 & 거듭제곱
8058	이항 계수 쿼리	CSES	보통	팩토리얼 역원 전처리 & 조합론
8059	피보나치 수열	CSES	보통	행렬 거듭제곱 & 분할 정복
8060	님 게임	CSES	보통	게임 이론 & 그룬디 XOR 합