C++ 수학 알고리즘 완벽 가이드 | GCD·LCM·소수·모듈러·행렬·FFT [실전]

· 35분 읽기 · 수정 고급 실습
C++ 수학 알고리즘 완벽 가이드 | GCD·LCM·소수·모듈러·행렬·FFT [실전]

이 글의 핵심

C++ 수학 알고리즘: 에라토스테네스 체, 유클리드 알고리즘, 모듈러 거듭제곱, 행렬 연산, FFT. 문제 시나리오, 완전한 예제, 흔한 실수, 성능 팁, 프로덕션 패턴. 분수를 기약분수로 만들거나, 큰 수의 거듭제곱을 모듈러 연산으로 구할 때 단순 곱셈·나눗셈만 쓰면 오버플로우와 정밀도 문제에 빠집니다. 비유하면 "a×b를 먼저 계산한 뒤 mod를 취하는 것"과 "중간 결과마다 mod를 취하는 것"의 차이입니다.

들어가며: “분수 기약분수화가 오버플로우로 틀려요”

수학 알고리즘 선택의 함정

분수를 기약분수로 만들거나, 큰 수의 거듭제곱을 모듈러 연산으로 구할 때 단순 곱셈·나눗셈만 쓰면 오버플로우와 정밀도 문제에 빠집니다. 비유하면 “a×b를 먼저 계산한 뒤 mod를 취하는 것”과 “중간 결과마다 mod를 취하는 것”의 차이입니다.

flowchart TD
  subgraph wrong[❌ 단순 곱셈 후 mod]
    W1[a × b % mod] --> W2[a×b 오버플로우]
    W2 --> W3[잘못된 결과]
    W3 --> W4[디버깅 어려움]
  end
  subgraph right[✅ 모듈러 곱셈 활용]
    R1[(a % mod) × (b % mod) % mod] --> R2[또는 128비트 활용]
    R2 --> R3[안전한 계산]
    R3 --> R4[암호화·코딩테스트 통과]
  end

이 글에서는 실제로 겪는 문제 시나리오부터 시작해, GCD·LCM, 소수 판별·에라토스테네스 체, 모듈러 연산·거듭제곱, 행렬 연산, FFT의 완전한 구현, 자주 하는 실수, 성능 최적화 팁, 프로덕션 패턴까지 단계별로 다룹니다.

이 글을 읽으면:

  • 수학 알고리즘의 핵심 개념을 이해할 수 있습니다.
  • GCD, LCM, 소수, 모듈러, 행렬을 실전에 활용할 수 있습니다.
  • 오버플로우·정밀도 문제를 피할 수 있습니다.

요구 환경: C++17 이상

실무 적용 경험: 이 글은 대규모 C++ 프로젝트에서 실제로 겪은 문제와 해결 과정을 바탕으로 작성되었습니다. 책이나 문서에서 다루지 않는 실전 함정과 디버깅 팁을 포함합니다.

목차

  1. 문제 시나리오
  2. 기본 개념
  3. 완전한 수학 알고리즘 예제
  4. 자주 발생하는 에러와 해결법
  5. 성능 최적화 팁
  6. 프로덕션 패턴
  7. 구현 체크리스트

1. 문제 시나리오

시나리오 1: 분수 기약분수화 오버플로우

상황: 분수 a/b를 기약분수로 만들려고 a/gcd(a,b), b/gcd(a,b)를 계산하는데, a·b가 10^18 수준이면 중간 곱셈에서 오버플로우가 납니다.

잘못된 접근: (a * b) % mod처럼 먼저 곱한 뒤 나누면 a * b 자체가 64비트를 넘깁니다.

해결: 유클리드 알고리즘으로 GCD를 구하고, 모듈러 역원 또는 128비트(__int128)를 활용해 안전하게 계산합니다.

시나리오 2: 소수 판별이 너무 느림

상황: 1~10^6 범위에서 소수 개수를 세어야 하는데, 각 수마다 O(√n) 판별을 하면 시간 초과입니다.

잘못된 접근: n이 소수인지 for (i=2; i*i<=n; i++)로 하나씩 검사하면 O(n√n)입니다.

해결: 에라토스테네스의 체로 O(n log log n)에 모든 소수를 한 번에 구합니다.

시나리오 3: 거듭제곱 mod 연산 시간 초과

상황: a^b % mod를 구해야 하는데, b가 10^18이라 for 루프로 b번 곱하면 당연히 시간 초과입니다.

잘못된 접근: pow(a, b) % mod는 부동소수점 오차와 오버플로우 문제가 있습니다.

해결: 빠른 거듭제곱(분할 정복)으로 O(log b)에 구합니다.

시나리오 4: 행렬 거듭제곱으로 피보나치

상황: fib(n)을 O(log n)에 구해야 합니다. n이 10^18이면 선형 DP로는 불가능합니다.

잘못된 접근: dp[i] = dp[i-1] + dp[i-2]로 n번 반복하면 n이 클 때 불가능합니다.

해결: 행렬 거듭제곱으로 [fib(n+1), fib(n)]^T = M^n × [1, 0]^T를 O(log n)에 계산합니다.

시나리오 5: 다항식 곱셈이 O(n²)로 느림

상황: 두 다항식의 곱을 구해야 하는데, 계수가 10^5 차수라 O(n²) 곱셈은 시간 초과입니다.

잘못된 접근: 이중 for 루프로 각 계수끼리 곱하면 O(n²)입니다.

해결: FFT(고속 푸리에 변환)로 O(n log n)에 곱셈을 수행합니다.

시나리오 6: 모듈러 역원이 필요한데 나눗셈

상황: (a / b) % mod를 구해야 하는데, 모듈러 연산에서는 나눗셈이 정의되지 않습니다.

잘못된 접근: (a % mod) / (b % mod)는 수학적으로 잘못된 결과를 냅니다.

해결: b의 모듈러 역원 b^(-1)을 구해 a * b^(-1) % mod로 계산합니다. (mod가 소수면 페르마 소정리 활용)

알고리즘 선택 가이드

문제 유형추천 기법시간 복잡도
최대공약수/최소공배수유클리드 알고리즘O(log min(a,b))
소수 판별 (단일)trial divisionO(√n)
소수 목록 (범위)에라토스테네스 체O(n log log n)
a^b % mod빠른 거듭제곱O(log b)
모듈러 역원확장 유클리드 / 페르마O(log mod)
행렬 거듭제곱분할 정복O(k³ log n)
다항식 곱셈FFTO(n log n)

2. 기본 개념

2.1 수학 알고리즘의 핵심 원리

flowchart LR
  subgraph core[핵심 원리]
    A[GCD] --> A1[유클리드: gcd(a,b)=gcd(b,a%b)]
    B[소수] --> B1[에라토스테네스: 배수 제거]
    C[모듈러] --> C1[(a×b)%m = ((a%m)×(b%m))%m]
    D[행렬] --> D1[M^n = M^(n/2)×M^(n/2)]
  end

2.2 GCD·LCM 관계

// gcd(a, b) × lcm(a, b) = a × b
// 따라서 lcm(a, b) = a × b / gcd(a, b)
// 주의: a*b에서 오버플로우 가능 → lcm = a / gcd(a,b) * b

3. 완전한 수학 알고리즘 예제

3.1 GCD (최대공약수) - 유클리드 알고리즘

문제: 두 정수 a, b의 최대공약수를 구합니다.

원리: gcd(a, b) = gcd(b, a % b). b가 0이 될 때까지 반복하면 a가 GCD입니다.

#include <cstdint>

// 반복문 버전 (권장: 스택 오버플로우 없음)
// 시간: O(log min(a,b))
int64_t gcd_iter(int64_t a, int64_t b) {
    a = std::abs(a);
    b = std::abs(b);
    while (b != 0) {
        int64_t t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// 재귀 버전
int64_t gcd_rec(int64_t a, int64_t b) {
    return b == 0 ? std::abs(a) : gcd_rec(b, a % b);
}

// C++17: std::gcd, std::lcm 사용 가능
#include <numeric>
// int64_t g = std::gcd(a, b);
// int64_t l = std::lcm(a, b);

3.2 LCM (최소공배수)

문제: 두 정수 a, b의 최소공배수를 구합니다. 오버플로우를 피해야 합니다.

// 오버플로우 방지: 먼저 나누고 곱하기
// lcm(a,b) = a * (b / gcd(a,b))
int64_t lcm_safe(int64_t a, int64_t b) {
    if (a == 0 || b == 0) return 0;
    int64_t g = gcd_iter(a, b);
    // a/g * b 는 g로 나눠지므로 정수. 순서 중요!
    return (a / g) * b;  // (a/g)*b 는 a*b/g 와 같지만 오버플로우 없음
}

// 여러 수의 LCM
int64_t lcm_range(const std::vector<int64_t>& arr) {
    int64_t result = 1;
    for (int64_t x : arr) {
        result = lcm_safe(result, x);
        if (result == 0) break;
    }
    return result;
}

3.3 확장 유클리드 - 베주 항등식과 모듈러 역원

문제: ax + by = gcd(a, b)를 만족하는 x, y를 구합니다. 모듈러 역원 계산에 사용됩니다.

// 확장 유클리드: ax + by = gcd(a,b) 의 x, y 반환
// 반환값: gcd(a, b)
int64_t ext_gcd(int64_t a, int64_t b, int64_t& x, int64_t& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int64_t x1, y1;
    int64_t g = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 모듈러 역원: a^(-1) mod m (gcd(a,m)=1 일 때)
// ax ≡ 1 (mod m) 인 x
int64_t mod_inverse(int64_t a, int64_t m) {
    int64_t x, y;
    int64_t g = ext_gcd((a % m + m) % m, m, x, y);
    if (g != 1) return -1;  // 역원 없음
    return (x % m + m) % m;
}

3.4 소수 판별 (단일 수)

문제: 주어진 n이 소수인지 판별합니다.

#include <cmath>

// Trial division: O(√n)
bool is_prime_trial(int64_t n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int64_t i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

// 6k±1 최적화: 2,3 배수 건너뛰기

3.5 에라토스테네스의 체

문제: 2 ~ n 범위의 모든 소수를 구합니다.

#include <vector>

// 에라토스테네스의 체: O(n log log n)
std::vector<int> sieve_of_eratosthenes(int n) {
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= n; j += i) {
            is_prime[j] = false;
        }
    }
    std::vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) primes.push_back(i);
    }
    return primes;
}

// 소수 개수만 세기 (메모리 절약: 비트 활용)
int count_primes(int n) {
    if (n < 2) return 0;
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= n; j += i)
            is_prime[j] = false;
    }
    int count = 0;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i]) ++count;
    return count;
}

3.6 모듈러 연산과 빠른 거듭제곱

문제: a^b % mod를 O(log b)에 구합니다.

// 빠른 거듭제곱 (분할 정복)
// a^b = (a^(b/2))^2 * a^(b%2)
int64_t mod_pow(int64_t a, int64_t b, int64_t mod) {
    if (mod == 1) return 0;
    int64_t result = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) {
            result = (result * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return result;
}

// 모듈러 곱셈 (오버플로우 방지)
// a * b % mod 를 64비트만으로 안전하게
int64_t mod_mul(int64_t a, int64_t b, int64_t mod) {
    a %= mod;
    b %= mod;
    int64_t result = 0;
    while (b > 0) {
        if (b & 1) {
            result = (result + a) % mod;
        }
        a = (a * 2) % mod;
        b >>= 1;
    }
    return result;
}

// __int128 사용 (GCC/Clang)
int64_t mod_mul_128(int64_t a, int64_t b, int64_t mod) {
    return static_cast<int64_t>((__int128)a * b % mod);
}

3.7 페르마 소정리를 이용한 모듈러 역원

문제: mod가 소수 p일 때, a^(-1) ≡ a^(p-2) (mod p)입니다.

// mod가 소수일 때: a^(-1) = a^(p-2) mod p
int64_t mod_inverse_fermat(int64_t a, int64_t p) {
    return mod_pow(a, p - 2, p);
}

// nCr % p (p 소수): 팩토리얼 역원 전처리
// nCr = n! / (r! * (n-r)!) → n! * inv(r!) * inv((n-r)!)

3.8 행렬 연산과 행렬 거듭제곱

문제: k×k 행렬 M의 n제곱을 O(k³ log n)에 구합니다.

#include <vector>

using Matrix = std::vector<std::vector<int64_t>>;
const int64_t MOD = 1'000'000'007;

// 행렬 곱셈: A * B
Matrix mat_mul(const Matrix& A, const Matrix& B) {
    int n = static_cast<int>(A.size());
    int m = static_cast<int>(A[0].size());
    int p = static_cast<int>(B[0].size());
    Matrix C(n, std::vector<int64_t>(p, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < p; ++j) {
            for (int k = 0; k < m; ++k) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    return C;
}

// 행렬 거듭제곱: M^n
Matrix mat_pow(Matrix M, int64_t n) {
    int k = static_cast<int>(M.size());
    Matrix result(k, std::vector<int64_t>(k, 0));
    for (int i = 0; i < k; ++i) result[i][i] = 1;  // 단위행렬
    while (n > 0) {
        if (n & 1) result = mat_mul(result, M);
        M = mat_mul(M, M);
        n >>= 1;
    }
    return result;
}

// 피보나치: fib(n) = M^(n-1)[0][0], M = [[1,1],[1,0]]
int64_t fib_matrix(int64_t n) {
    if (n <= 1) return n;
    Matrix M = {{1, 1}, {1, 0}};
    Matrix Mn = mat_pow(M, n - 1);
    return Mn[0][0];
}

3.9 소인수 분해

문제: 주어진 n을 소인수로 분해합니다. 소수 목록이 있으면 더 빠릅니다.

// Trial division으로 소인수 분해
std::vector<std::pair<int64_t, int>> factorize(int64_t n) {
    std::vector<std::pair<int64_t, int>> factors;
    for (int64_t i = 2; i * i <= n; ++i) {
        if (n % i != 0) continue;
        int cnt = 0;
        while (n % i == 0) {
            n /= i;
            ++cnt;
        }
        factors.emplace_back(i, cnt);
    }
    if (n > 1) factors.emplace_back(n, 1);
    return factors;
}

// 약수 개수: (e1+1)*(e2+1)*... (각 소인수 지수+1의 곱)
int count_divisors(int64_t n) {
    auto factors = factorize(n);
    int result = 1;
    for (const auto& [p, e] : factors) result *= (e + 1);
    return result;
}

3.10 FFT (고속 푸리에 변환) 개요

문제: 두 다항식의 곱을 O(n log n)에 구합니다.

// FFT는 복소수 연산과 분할 정복을 이용
// Cooley-Tukey 알고리즘이 대표적
// 실전에서는 FFT 라이브러리(kactl, atcoder 등) 사용 권장

#include <complex>
#include <vector>

using Complex = std::complex<double>;
const double PI = 3.14159265358979323846;

void fft(std::vector<Complex>& a, bool invert) {
    int n = static_cast<int>(a.size());
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n >> 1;
        for (; j >= bit; bit >>= 1) j -= bit;
        j += bit;
        if (i < j) std::swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1) {
        double angle = 2 * PI / len * (invert ? -1 : 1);
        Complex wlen(std::cos(angle), std::sin(angle));
        for (int i = 0; i < n; i += len) {
            Complex w(1);
            for (int j = 0; j < len / 2; ++j) {
                Complex u = a[i + j], v = a[i + j + len/2] * w;
                a[i + j] = u + v;
                a[i + j + len/2] = u - v;
                w *= wlen;
            }
        }
    }
    if (invert) {
        for (int i = 0; i < n; ++i) a[i] /= n;
    }
}

std::vector<int64_t> multiply_poly(const std::vector<int64_t>& a,
                                   const std::vector<int64_t>& b) {
    int n = 1;
    while (n < static_cast<int>(a.size()) + static_cast<int>(b.size())) n <<= 1;
    std::vector<Complex> fa(n), fb(n);
    for (size_t i = 0; i < a.size(); ++i) fa[i] = a[i];
    for (size_t i = 0; i < b.size(); ++i) fb[i] = b[i];
    fft(fa, false);
    fft(fb, false);
    for (int i = 0; i < n; ++i) fa[i] *= fb[i];
    fft(fa, true);
    std::vector<int64_t> result(n);
    for (int i = 0; i < n; ++i) {
        result[i] = static_cast<int64_t>(std::round(fa[i].real()));
    }
    return result;
}

4. 자주 발생하는 에러와 해결법

에러 1: 모듈러 연산에서 오버플로우

증상: (a * b) % mod 계산 시 잘못된 결과 또는 런타임 에러.

원인: a * b가 int64_t 범위를 넘깁니다.

// ❌ 잘못된 코드
int64_t bad = (a * b) % mod;  // a*b 오버플로우

// ✅ 해결 1: mod_mul 사용
int64_t good = mod_mul(a, b, mod);

// ✅ 해결 2: __int128 (GCC/Clang)
int64_t good2 = static_cast<int64_t>((__int128)a * b % mod);

에러 2: LCM 계산 시 오버플로우

증상: lcm(a, b) = a * b / gcd(a, b)에서 오버플로우.

원인: a * b가 먼저 계산됩니다.

// ❌ 잘못된 코드
int64_t bad = a * b / gcd(a, b);  // a*b 오버플로우

// ✅ 올바른 코드: 먼저 나누고 곱하기
int64_t good = (a / gcd(a, b)) * b;

에러 3: 음수 mod 연산

증상: -5 % 3이 C++에서 -2를 반환합니다. (수학적으로는 1)

원인: C++의 %는 피제수의 부호를 따릅니다.

// ❌ 잘못된 가정
int r = -5 % 3;  // r = -2 (C++)

// ✅ 올바른 모듈러 결과 (0 ~ mod-1)
int64_t mod_positive(int64_t a, int64_t m) {
    return (a % m + m) % m;
}

에러 4: 소수 판별에서 i*i 오버플로우

증상: for (i = 2; i * i <= n; i++)에서 n이 크면 i*i 오버플로우.

원인: i가 약 3e9를 넘으면 i*i가 64비트를 넘깁니다.

// ❌ 잘못된 코드 (n이 10^18일 때)
for (int64_t i = 2; i * i <= n; ++i)  // i*i 오버플로우

// ✅ 올바른 코드
for (int64_t i = 2; i <= n / i; ++i)
// 또는
for (int64_t i = 2; i <= static_cast<int64_t>(std::sqrt(n)); ++i)

에러 5: 모듈러 역원이 존재하지 않을 때

증상: gcd(a, m) != 1일 때 역원이 없는데 -1 등을 반환하지 않아 잘못된 결과 사용.

원인: 역원은 gcd(a, m) = 1일 때만 존재합니다.

// ✅ 역원 계산 전 검증
int64_t inv = mod_inverse(a, m);
if (inv == -1) {
    // 역원 없음 - 다른 방법 사용 (확장 유클리드 등)
    return ERROR;
}

에러 6: 에라토스테네스 체에서 i*i 시작점

증상: for (int j = i * 2; j <= n; j += i)로 하면 이미 지운 배수를 다시 방문해 비효율적.

원인: 2i, 3i, ..., (i-1)i는 이미 더 작은 소수의 배수로 지워졌습니다.

// ❌ 비효율 (동작은 함)
for (int j = i * 2; j <= n; j += i)

// ✅ 올바른 최적화: i*i부터 시작
for (int j = i * i; j <= n; j += i)

에러 7: 빠른 거듭제곱에서 mod 1

증상: mod = 1일 때 result = 1이 반환되어 기대와 다를 수 있음.

원인: a % 1 = 0이므로 0^b = 0이어야 하는데, 루프에서 result = 1로 시작하면 1이 반환됩니다.

// ✅ mod 1 처리
int64_t mod_pow(int64_t a, int64_t b, int64_t mod) {
    if (mod == 1) return 0;  // 모든 수 mod 1 = 0
    // ...
}

에러 8: GCD에 0 입력

증상: gcd(0, 0) 호출 시 무한 루프 또는 정의되지 않은 동작.

원인: 수학적으로 gcd(0, 0)은 정의되지 않습니다.

// ✅ 0 처리
int64_t gcd_safe(int64_t a, int64_t b) {
    if (a == 0 && b == 0) return 0;  // 또는 예외
    return gcd_iter(a, b);
}

에러 9: 행렬 곱셈 차원 불일치

증상: A(m×n) * B(p×q)에서 n≠p일 때 인덱스 초과.

원인: 행렬 곱셈은 A의 열 수와 B의 행 수가 같아야 합니다.

// ✅ 차원 검증
Matrix mat_mul_safe(const Matrix& A, const Matrix& B) {
    if (A.empty() || B.empty() || A[0].size() != B.size())
        throw std::invalid_argument("Invalid matrix dimensions");
    // ...
}

5. 성능 최적화 팁

5.1 에라토스테네스 체 최적화

// 짝수 최적화: 2만 따로 처리, 홀수만 체크
std::vector<int> sieve_optimized(int n) {
    if (n < 2) return {};
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 4; i <= n; i += 2) is_prime[i] = false;
    for (int i = 3; i * i <= n; i += 2) {
        if (!is_prime[i]) continue;
        for (int j = i * i; j <= n; j += 2 * i)  // 홀수 배수만
            is_prime[j] = false;
    }
    std::vector<int> primes = {2};
    for (int i = 3; i <= n; i += 2)
        if (is_prime[i]) primes.push_back(i);
    return primes;
}

5.2 메모리 절약: 비트 풀

// bool 대신 비트로 압축 (8배 절약)
#include <bitset>

std::vector<int> sieve_bitset(int n) {
    std::vector<uint8_t> is_prime((n + 8) / 8, 0xFF);
    is_prime[0] &= ~3;  // 0, 1 제거
    for (int i = 2; i * i <= n; ++i) {
        if (!(is_prime[i / 8] & (1 << (i % 8)))) continue;
        for (int j = i * i; j <= n; j += i)
            is_prime[j / 8] &= ~(1 << (j % 8));
    }
    std::vector<int> primes;
    for (int i = 2; i <= n; ++i)
        if (is_prime[i / 8] & (1 << (i % 8)))
            primes.push_back(i);
    return primes;
}

5.3 행렬 곱셈 캐시 친화적 순서

// i-j-k 순서가 캐시에 유리 (일반적)
// k를 안쪽 루프로 두면 B의 같은 행을 반복 접근
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < p; ++j) {
        int64_t sum = 0;
        for (int k = 0; k < m; ++k) {
            sum += A[i][k] * B[k][j];
        }
        C[i][j] = sum % MOD;
    }
}

5.4 컴파일 타임 상수 활용

// mod가 컴파일 타임 상수면 컴파일러 최적화 유리
template <int64_t Mod>
struct ModInt {
    int64_t v;
    ModInt(int64_t x = 0) : v((x % Mod + Mod) % Mod) {}
    ModInt operator*(ModInt o) const {
        return ModInt(static_cast<int64_t>((__int128)v * o.v % Mod));
    }
    // ...
};

5.5 성능 비교 요약

연산나이브최적화비고
GCDO(min(a,b))O(log min(a,b))유클리드
소수 n개O(n√n)O(n log log n)에라토스테네스
a^b modO(b)O(log b)빠른 거듭제곱
행렬 M^nO(k³ n)O(k³ log n)분할 정복
다항식 곱O(n²)O(n log n)FFT

6. 프로덕션 패턴

6.1 모듈러 연산 래퍼 클래스

template <int64_t Mod>
struct ModInt {
    int64_t v;
    ModInt(int64_t x = 0) : v((x % Mod + Mod) % Mod) {}
    ModInt& operator+=(ModInt o) { v = (v + o.v) % Mod; return *this; }
    ModInt& operator-=(ModInt o) { v = (v - o.v + Mod) % Mod; return *this; }
    ModInt& operator*=(ModInt o) {
        v = static_cast<int64_t>((__int128)v * o.v % Mod);
        return *this;
    }
    ModInt operator+(ModInt o) const { return ModInt(*this) += o; }
    ModInt operator-(ModInt o) const { return ModInt(*this) -= o; }
    ModInt operator*(ModInt o) const { return ModInt(*this) *= o; }
    ModInt pow(int64_t b) const {
        ModInt r(1), a(*this);
        for (; b; b >>= 1, a *= a) if (b & 1) r *= a;
        return r;
    }
    ModInt inv() const { return pow(Mod - 2); }  // 페르마 (Mod 소수일 때)
};

using Mint = ModInt<1'000'000'007>;

6.2 소수·팩토리얼 전처리

// nCr, nPr 등에 필요한 팩토리얼·역원 전처리
struct FactorialPrecompute {
    std::vector<Mint> fact, inv_fact;
    FactorialPrecompute(int n) : fact(n + 1), inv_fact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        inv_fact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) inv_fact[i - 1] = inv_fact[i] * i;
    }
    Mint nCr(int n, int r) {
        if (r < 0 || r > n) return 0;
        return fact[n] * inv_fact[r] * inv_fact[n - r];
    }
};

6.3 에러 처리와 검증

// GCD 기반 검증
int64_t safe_lcm(int64_t a, int64_t b) {
    if (a == 0 && b == 0) return 0;
    if (a == 0 || b == 0) {
        // 로깅: 0이 입력됨
        return 0;
    }
    int64_t g = gcd_iter(std::abs(a), std::abs(b));
    if ((a / g) > INT64_MAX / std::abs(b)) {
        // 오버플로우 가능성 로깅
        throw std::overflow_error("LCM overflow");
    }
    return (a / g) * b;
}

6.4 단위 테스트용 테스트 케이스

// 검증용 예시
void test_math_algorithms() {
    assert(gcd_iter(48, 18) == 6);
    assert(gcd_iter(0, 5) == 5);
    assert(lcm_safe(12, 18) == 36);
    assert(is_prime_trial(97) == true);
    assert(is_prime_trial(100) == false);
    assert(mod_pow(2, 10, 1000) == 24);
    assert(mod_inverse_fermat(3, 7) == 5);  // 3*5=15≡1 (mod 7)
    assert(fib_matrix(10) == 55);
}

6.5 알고리즘 선택 플로우

flowchart TD
    A[수학 문제] --> B{문제 유형}
    B -->|최대공약수/배수| C[유클리드]
    B -->|소수 범위| D[에라토스테네스]
    B -->|소수 단일| E[Trial division]
    B -->|a^b mod| F[빠른 거듭제곱]
    B -->|나눗셈 mod| G[모듈러 역원]
    B -->|선형 점화식| H[행렬 거듭제곱]
    B -->|다항식 곱| I[FFT]

6.6 실전 활용 예시: nCr % p

상황: 조합 수 nCr을 소수 p로 나눈 나머지를 구합니다. n, r이 10^6 수준.

// 전처리 O(n), 쿼리 O(1)
struct Comb {
    std::vector<Mint> fact, inv_fact;
    Comb(int n) : fact(n + 1), inv_fact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        inv_fact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) inv_fact[i - 1] = inv_fact[i] * i;
    }
    Mint operator()(int n, int r) {
        if (r < 0 || r > n) return 0;
        return fact[n] * inv_fact[r] * inv_fact[n - r];
    }
};

6.7 실전 활용 예시: 기약분수화

상황: 분수 a/b를 기약분수로 만듭니다. a, b가 10^18까지.

std::pair<int64_t, int64_t> to_irreducible(int64_t a, int64_t b) {
    if (b == 0) throw std::invalid_argument("denominator is zero");
    int64_t g = gcd_iter(std::abs(a), std::abs(b));
    a /= g;
    b /= g;
    if (b < 0) { a = -a; b = -b; }  // 분모를 양수로
    return {a, b};
}

6.8 실전 활용 예시: RSA 스타일 거듭제곱

상황: 암호화에서 m^e % n을 안전하게 계산합니다.

// 큰 수에도 안전: __int128 또는 mod_mul 활용
int64_t rsa_pow(int64_t m, int64_t e, int64_t n) {
    return mod_pow(m, e, n);  // 내부에서 mod_mul 사용 권장
}

7. 구현 체크리스트

GCD·LCM

  • 유클리드 알고리즘 (반복문 권장)
  • LCM 시 (a/gcd)*b 순서로 오버플로우 방지
  • 음수 입력 처리 (std::abs)

소수

  • 단일: trial division, i <= n/i 오버플로우 방지
  • 범위: 에라토스테네스 체, j = i*i부터 시작
  • 2, 3 배수 건너뛰기 (6k±1) 선택 적용

모듈러 연산

  • (a % m + m) % m으로 음수 처리
  • 곱셈: mod_mul 또는 __int128 사용
  • 거듭제곱: 빠른 거듭제곱 O(log b)
  • 역원: gcd(a,m)=1 확인

행렬

  • 단위행렬로 거듭제곱 초기화
  • 곱셈 시 mod 적용
  • 행렬 크기 k³에 주의 (k가 크면 병목)

일반

  • 모든 코드 블록에 언어 태그 지정
  • 경계 조건 (0, 음수, 오버플로우) 테스트
  • 프로덕션에서는 ModInt 등 래퍼 사용 검토

정리

항목설명
GCD/LCM유클리드 O(log n), LCM은 나눗셈 먼저
소수단일: trial, 범위: 에라토스테네스 체
모듈러오버플로우 방지, 빠른 거듭제곱, 역원
행렬분할 정복 거듭제곱 O(k³ log n)
FFT다항식 곱 O(n log n)

핵심 원칙:

  1. 오버플로우를 항상 염두에 둡니다.
  2. 모듈러 연산은 중간 결과마다 적용합니다.
  3. 소수·팩토리얼은 전처리로 재사용합니다.
  4. 프로덕션에서는 래퍼 클래스로 안전성을 높입니다.

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 암호화(RSA, 디피-헬만), 신호 처리(FFT), 과학 계산(행렬 연산), 코딩 테스트(수학 유형), 게임(난수·확률) 등에 활용합니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference의 <numeric>(gcd, lcm), 수학 라이브러리 문서를 참고하세요. FFT는 KACTL, AtCoder 라이브러리 등 검증된 구현을 사용하는 것을 권장합니다.

Q. 오버플로우를 피하는 가장 좋은 방법은?

A. 1) __int128 사용 (GCC/Clang), 2) mod_mul처럼 덧셈으로 분해, 3) ModInt 래퍼로 연산을 캡슐화하는 방법이 있습니다. 프로덕션에서는 래퍼 클래스가 가장 안전합니다.

한 줄 요약: GCD·LCM·소수·모듈러·행렬·FFT를 실전에서 안전하게 활용할 수 있습니다.

관련 글

  • C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]
  • C++ Algorithm Numeric |
  • C++ 알고리즘 |
... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3