기본 원리: 중국인의 나머지 정리 (CRT)
주어진 연립 동치식을 만족하는 해 x를 찾는 문제이다:
\[
\begin{cases}
x \equiv a_1 \pmod{r_1} \\
x \equiv a_2 \pmod{r_2} \\
\vdots \\
x \equiv a_n \pmod{r_n}
\end{cases}
\]
여기서 각 모듈러스 \( r_i \)들은 서로소일 경우, 이 시스템은 유일한 해를 가진다. 이를 통해 전체 해를 구성할 수 있다.
각 \( i \)에 대해 \( A_i = \prod_{j \ne i} r_j \)로 정의하고, \( A_i \)와 \( r_i \)가 서로소이므로 \( A_i \)의 모듈러 역원 \( c_i \)가 존재한다. 즉,
\[
c_i \cdot A_i \equiv 1 \pmod{r_i}
\]
해의 구성 요소는 \( x_i = c_i \cdot A_i \cdot a_i \)이며, 이때
- \( x_i \equiv a_i \pmod{r_i} \)
- \( x_i \equiv 0 \pmod{r_j} \) (\( j \ne i \))
따라서 전체 해는 모든 \( x_i \)의 합으로 표현되며, 전체 곱 \( R = \prod_{i=1}^n r_i \)에 대해 임의의 정수 \( p \)에 대해
\[
x = \sum_{i=1}^n c_i \cdot A_i \cdot a_i + p \cdot R
\]
가 된다.
확장된 중국인의 나머지 정리 (exCRT): 서로소 조건 없이 처리
모듈러스가 서로소가 아닐 때도 가능한 해를 찾기 위해 사용된다. 핵심 아이디어는 두 개의 동치식을 반복적으로 병합하여 하나의 동치식으로 줄이는 것이다.
두 식:
\[
\begin{cases}
x \equiv a_1 \pmod{r_1} \\
x \equiv a_2 \pmod{r_2}
\end{cases}
\]
이를 통합하여 새로운 형식 \( x \equiv a \pmod{\text{lcm}(r_1, r_2)} \)로 변환한다.
각 방정식을 등식으로 표현하면:
\[
x = a_1 + s_1 \cdot r_1 = a_2 + s_2 \cdot r_2
\]
이로부터 다음을 얻는다:
\[
s_1 \cdot r_1 - s_2 \cdot r_2 = a_2 - a_1
\]
이 일차방정식은 확장 유클리드 알고리즘으로 풀 수 있으며, 해가 존재하지 않으면 전체 시스템은 불가능하다. 해가 존재하면 \( s_1 \)의 일반해는 다음과 같다:
\[
s_1 = s_1' + k \cdot \frac{r_2}{\gcd(r_1, r_2)}
\]
이를 원래 식에 대입하면:
\[
x = a_1 + s_1' \cdot r_1 + k \cdot \text{lcm}(r_1, r_2)
\]
즉,
\[
x \equiv a_1 + s_1' \cdot r_1 \pmod{\text{lcm}(r_1, r_2)}
\]
이렇게 하여 두 방정식을 하나의 방정식으로 축소할 수 있다.
코드 구현 (확장형)
// 확장 유클리드 알고리즘
LL extended_gcd(LL a, LL b, LL &x, LL &y) {
if (!b) {
x = 1; y = 0;
return a;
}
LL d = extended_gcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
// 확장 중국인의 나머지 정리
LL ex_crt(int n, LL a[], LL r[]) {
for (int i = 1; i < n; ++i) {
LL x, y, g;
g = extended_gcd(r[i], r[i+1], x, y);
// a[i] <= a[i+1] 보장 (순서 조정)
if (a[i] > a[i+1]) {
std::swap(a[i], a[i+1]);
std::swap(r[i], r[i+1]);
}
// 불가능한 경우: (a[i+1] - a[i])가 gcd로 나누어떨어지지 않음
if ((a[i+1] - a[i]) % g != 0) return -1;
// 새로운 모듈러스: lcm(r[i], r[i+1])
LL lcm_val = r[i] / g * r[i+1];
// 새로운 해: a[i] + x * r[i] (모듈러 새 값)
LL new_a = (a[i] + x * r[i] % lcm_val) % lcm_val;
// 업데이트
r[i+1] = lcm_val;
a[i+1] = new_a;
}
return a[n];
}