정수론의 핵심 원리와 알고리즘 구현

1. 기초 연산 및 약수와 배수

1.1 나머지 연산 (Modular Arithmetic)

나머지 연산은 다음과 같은 분배 법칙이 성립합니다.

  • $(a + b) \pmod c = ((a \pmod c) + (b \pmod c)) \pmod c$
  • $(a - b) \pmod c = ((a \pmod c) - (b \pmod c) + c) \pmod c$
  • $(a \times b) \pmod c = ((a \pmod c) \times (b \pmod c)) \pmod c$

1.2 약수와 배수 (Divisibility)

정수 $a, b$에 대해 $b = a \times c$를 만족하는 정수 $c$가 존재하면 $a$는 $b$를 나누며, 이를 $a \mid b$라고 표기합니다. 이때 $a$는 $b$의 약수, $b$는 $a$의 배수입니다.

  • $a \mid b$ 이고 $b \mid c$ 이면 $a \mid c$ 입니다.
  • $a \mid b$ 이고 $b \mid a$ 이면 $|a| = |b|$ 입니다.

2. 최대공약수 (GCD)

2.1 유클리드 호제법

가장 널리 쓰이는 알고리즘으로 시간 복잡도는 $O(\log n)$입니다.

long long get_gcd(long long n1, long long n2) {
    while (n2 != 0) {
        n1 %= n2;
        long long temp = n1;
        n1 = n2;
        n2 = temp;
    }
    return n1;
}

2.2 Binary GCD (Stein's Algorithm)

나눗셈 연산 없이 비트 연산만으로 GCD를 구하여 효율성을 높인 방식입니다.

int fast_gcd(int x, int y) {
    if (!x || !y) return x | y;
    int shift = __builtin_ctz(x | y);
    x >>= __builtin_ctz(x);
    while (y) {
        y >>= __builtin_ctz(y);
        if (x > y) {
            int temp = x;
            x = y;
            y = temp;
        }
        y -= x;
    }
    return x << shift;
}

3. 거듭제곱과 소수

3.1 빠른 거듭제곱 (Binary Exponentiation)

분할 정복을 이용하여 $a^b \pmod p$를 $O(\log b)$ 시간에 계산합니다.

long long power_mod(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

3.2 소수 판별: 밀러-라빈 (Miller-Rabin)

큰 수에 대해 확률적으로 소수 여부를 판별하는 알고리즘입니다.

bool miller_rabin(long long n, long long a) {
    if (a % n == 0) return true;
    long long d = n - 1;
    while (d % 2 == 0) {
        if (power_mod(a, d, n) == n - 1) return true;
        d /= 2;
    }
    long long res = power_mod(a, d, n);
    return res == n - 1 || res == 1;
}

bool check_prime(long long n) {
    static const long long bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;
    for (long long a : bases) {
        if (n == a) return true;
        if (!miller_rabin(n, a)) return false;
    }
    return true;
}

4. 약수의 성질과 선형 체

4.1 약수의 개수와 합

$n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$일 때:

  • 약수의 개수: $d(n) = \prod (e_i + 1)$
  • 약수의 총합: $\sigma(n) = \prod \frac{p_i^{e_i+1}-1}{p_i-1}$

4.2 오일러 피 함수 (Euler's Totient Function)

$\varphi(n)$은 $n$ 이하의 자연수 중 $n$과 서로소인 수의 개수입니다.

int get_phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

5. 합동식과 모듈러 역원

5.1 페르마의 소정리

$p$가 소수이고 $a$가 $p$의 배수가 아닐 때, $a^{p-1} \equiv 1 \pmod p$ 이므로 역원은 $a^{p-2} \pmod p$입니다.

5.2 선형 역원 계산

1부터 $n$까지의 모든 역원을 $O(n)$ 시간에 구하는 방법입니다.

void precompute_inverses(int n, int p) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (long long)(p - p / i) * inv[p % i] % p;
    }
}

6. 확장 유클리드 알고리즘 (exgcd)

$ax + by = \gcd(a, b)$를 만족하는 정수해 $x, y$를 구합니다.

long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    long long x1, y1;
    long long d = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

7. BSGS (Baby-step Giant-step)

$a^x \equiv b \pmod p$에서 $x$를 구하는 알고리즘으로 $O(\sqrt{p})$의 시간이 소요됩니다.

long long solve_bsgs(long long a, long long b, long long p) {
    a %= p; b %= p;
    if (b == 1) return 0;
    long long m = ceil(sqrt(p));
    unordered_map<long long, long long> baby_steps;
    long long cur = b;
    for (int j = 0; j < m; j++) {
        baby_steps[cur] = j;
        cur = (cur * a) % p;
    }
    long long giant = power_mod(a, m, p);
    cur = giant;
    for (int i = 1; i <= m; i++) {
        if (baby_steps.count(cur)) {
            return i * m - baby_steps[cur];
        }
        cur = (cur * giant) % p;
    }
    return -1;
}

8. 가우스 소거법 (Gaussian Elimination)

선형 방정식 시스템을 상삼각 행렬로 변환하여 해를 구합니다.

int solve_gauss(vector<vector<double>> &matrix, int n, vector<double> &result) {
    for (int i = 0; i < n; i++) {
        int pivot = i;
        for (int j = i + 1; j < n; j++)
            if (abs(matrix[j][i]) > abs(matrix[pivot][i])) pivot = j;
        swap(matrix[i], matrix[pivot]);

        if (abs(matrix[i][i]) < 1e-9) continue;

        for (int j = 0; j < n; j++) {
            if (i != j) {
                double factor = matrix[j][i] / matrix[i][i];
                for (int k = i; k <= n; k++)
                    matrix[j][k] -= factor * matrix[i][k];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (abs(matrix[i][i]) < 1e-9 && abs(matrix[i][n]) > 1e-9) return 0; // 무해
        result[i] = matrix[i][n] / matrix[i][i];
    }
    return 1;
}

9. 행렬 거듭제곱과 점화식

피보나치 수열과 같은 선형 점화식은 행렬 거듭제곱을 통해 $O(\log n)$ 시간에 계산할 수 있습니다.

피보나치 수열 변환 행렬: $\begin{bmatrix} f_{n} \\ f_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f_{n-1} \\ f_{n-2} \end{bmatrix}$

태그: number theory Euclidean Algorithm Modular Inverse Primality Test Matrix Exponentiation

10월 31일 03:13에 게시됨