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

?

x가 존재하고 다음과 같은 식을 만족하는 x를 구해야함!
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)

위의 식에서 본다면 x는 8임을 확인할 수 있는데 이를 빠르게 구하기 위해서 중국인 나머지 정리를 활용한다.

증명?(더러움..)

• 다음과 같은 합동식이 존재한다고 하자!

• 두 합동식이 동시에 해를 가지기 위해서는 다음 조건을 만족해야함

• 만약 위의 조건이 성립하지 않으면 해는 존재하지 않음!
• 위의 조건을 성립하면 x를 다음과 같이 표현할 수 있음

• 위와 같이 표현 가능하고 다음과 같이 표현 가능하다.

• 이제 배주 항등식에 따라서 다음과 같은 식이 존재함을 확인할 수 있다!

• 이제 x를 최종적으로 도출한다면 다음과 같이 도출할 수 있다.

• 그러고 나서 다음의 배주 항등식을 활용하여서 대칭 구조로 나타낼 수 있다!

• q와 p와 같은 경우에는 확장 유클리드 알고리즘을 통해서 구할 수 있다!

활용

• 위의 내용은 두 개의 식에 대해서 설명해 본 것인데 만약 여러 개의 식이 나오면 어떻게 해야 하는 지 살펴보자!

BOJ 34036(걸어가요)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128;

tuple<ll, ll, ll> egcd(ll a, ll b) {
	if (b == 0) return { a, 1, 0 };
	auto [g, x1, y1] = egcd(b, a % b);
	return { g, y1, x1 - (a / b) * y1 };
}

//CRT
pair<ll, ll> CRT(vector<ll>& a, vector<ll>& m) {
	int n = a.size();
	ll a1 = a[0];
	ll m1 = m[0];
	a1 %= m1;
	for (int i = 1; i < n; i++) {
		ll a2 = a[i];
		ll m2 = m[i];
		ll g = gcd(m1, m2);
		if ((a2 - a1) % g != 0) return { -1, -1 };

		auto [_, p, q] = egcd(m1 / g, m2 / g);
		i128 mod = (i128)m1 / g * m2;

		i128 t1 = ((i128)a1 * (m2 / g) % mod) * q % mod; 
		i128 t2 = ((i128)a2 * (m1 / g) % mod) * p % mod;
		i128 res = (t1 + t2) % mod;
		if (res < 0) res += mod;

		a1 = (ll)res;
		m1 = (ll)mod;
	}
	return { a1, m1 };
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<ll> x(n), s(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> s[i];
	}

	auto [res, mod] = CRT(x, s);
	if (res == -1) cout << -1;
	else {
		ll mx = *max_element(x.begin(), x.end());
		if (res < mx) { 
            //res가 최대값 보다 작은 경우
            //mx보다 크게 만들어줌
			ll k = (mx - res + mod - 1) / mod;
			res += k * mod;
		}
		cout << res;
	}
}