[C++로 배우는 알고리즘과 자료구조 심화] Day 14: 중국인의 나머지 정리 (Chinese Remainder Theorem)

중국인의 나머지 정리 (Chinese Remainder Theorem, CRT)

중국인의 나머지 정리(CRT)는 서로 다른 소수들의 모듈러 시스템에서 주어진 나머지 값을 갖는 수를 찾는 방법입니다. CRT는 정수론과 암호학, 병렬 컴퓨팅 등 여러 분야에서 활용됩니다.

중국인의 나머지 정리

다음은 중국인의 나머지 정리의 기본 공식입니다:

주어진 서로 다른 정수 (n_1, n_2, \ldots, n_k)가 서로소(즉, (\gcd(n_i, n_j) = 1), (i \ne j))일 때, 다음과 같은 동시 합동식 시스템을 만족하는 유일한 정수 (x)가 존재합니다:

 

[\begin{cases}
x \equiv a_1 \pmod{n_1} \
x \equiv a_2 \pmod{n_2} \
\vdots \
x \equiv a_k \pmod{n_k}
\end{cases} ]

이때 (x)는 다음과 같이 구할 수 있습니다:

1. (N = n_1 \times n_2 \times \ldots \times n_k)
2. (N_i = \frac{N}{n_i})
3. (M_i = N_i^{-1} \pmod{n_i}) (즉, (N_i)의 모듈러 역수)
4. (x = \sum_{i=1}^{k} a_i \times N_i \times M_i \pmod{N})

여기서 (M_i)는 다음 조건을 만족하는 정수입니다:

[ N_i \times M_i \equiv 1 \pmod{n_i} ]

중국인의 나머지 정리 구현

다음은 C++로 중국인의 나머지 정리를 구현한 예제입니다.

 

모듈러 역수 계산 함수

#include <iostream>
#include <vector>

// 확장 유클리드 알고리즘을 사용한 모듈러 역수 계산 함수
int modInverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if (m == 1)
        return 0;

    while (a > 1) {
        q = a / m;
        t = m;
        m = a % m, a = t;
        t = x0;
        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0)
        x1 += m0;

    return x1;
}

 

중국인의 나머지 정리 함수

// 중국인의 나머지 정리 함수
int chineseRemainderTheorem(const std::vector<int>& num, const std::vector<int>& rem) {
    int k = num.size();
    int prod = 1;
    for (int i = 0; i < k; i++) {
        prod *= num[i];
    }

    int result = 0;

    for (int i = 0; i < k; i++) {
        int pp = prod / num[i];
        result += rem[i] * modInverse(pp, num[i]) * pp;
    }

    return result % prod;
}

 

사용 예제

int main() {
    std::vector<int> num = {3, 4, 5};
    std::vector<int> rem = {2, 3, 1};

    int result = chineseRemainderTheorem(num, rem);
    std::cout << "x의 값은 " << result << "입니다." << std::endl;

    return 0;
}

 

설명

1. modInverse 함수:
   • 확장 유클리드 알고리즘을 사용하여 모듈러 역수를 계산합니다.
   • (a \times x \equiv 1 \pmod{m})을 만족하는 (x)를 찾습니다.
2. chineseRemainderTheorem 함수:
   • 각 모듈러 값들의 곱인 (N)을 계산합니다.
   • 각 모듈러 값 (n_i)에 대해 (N_i)를 계산합니다.
   • 각 (N_i)의 모듈러 역수를 계산하여 (M_i)를 찾습니다.
   • 최종 결과 (x)를 계산합니다.
3. 사용 예제:
   • 주어진 모듈러 값들과 나머지 값들을 입력으로 받아 CRT를 사용하여 (x)를 계산합니다.

중국인의 나머지 정리의 개념과 구현 방법을 이해했습니다. 질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 15: 다차원 동적 계획법 (Multidimensional DP)"에 대해 학습하겠습니다.