백준 34036 - 중국인의 나머지 정리

 

중국인의 나머지 정리와 확장 유클리드의 개념을 이해하고 적용해보기 딱 좋은 문제입니다. ( 솔직히 이 문제는 이를 사용할 필요는 없습니다)

 

1. 중국인의 나머지 정리란?

 

중국인의 나머지 정리(Chinese Remainder Theorem, CRT)는 여러 개의 합동식을 동시에 만족시키는 정수 해를 찾는 방법입니다.

간단히 말해, 다음과 같은 문제를 푸는 데 사용됩니다.

"어떤 수 x를 3으로 나누면 나머지가 2이고, 5로 나누면 나머지가 3이다. 이 두 조건을 모두 만족하는 x는 무엇일까?"

 

이는 모두가 만나는 지점 P가 P ≡ Xᵢ (mod Sᵢ)라는 규칙을 만족해야 함을 의미합니다. 즉, 이 문제는 N개의 합동식을 동시에 만족시키는 가장 작은 P를 찾는 전형적인 중국인의 나머지 정리 문제입니다.

다만, 보폭 S_i들이 항상 서로소가 아니므로, 두 개의 합동식을 하나로 합쳐나가는 방식의 확장된 중국인의 나머지 정리가 필요합니다.

2. 확장 유클리드 호제법이란?

확장 유클리드 호제법(Extended Euclidean Algorithm)은 두 정수 a와 b의 최대공약수(gcd(a, b))를 구하는 동시에, ax + by = gcd(a, b) 라는 등식을 만족하는 정수 해 x와 y를 찾아내는 알고리즘입니다.

 

이것이 왜 필요할까요?

중국인의 나머지 정리를 푸는 과정에서 두 합동식 P ≡ a₁ (mod n₁)과 P ≡ a₂ (mod n₂)를 합치려면, k * n₁ ≡ a₂ - a₁ (mod n₂) 형태의 선형 합동 방정식을 풀어야 합니다. 확장 유클리드 호제법은 바로 이 방정식을 푸는 데 필요한 k 값을 계산하는 핵심적인 역할을 합니다. 

 

3. 풀이코드

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;

using namespace std;

ll gcd(ll a, ll b) {
	while (b) {
		a %= b;
		swap(a, b);
	}

	return a;
}

ll extendedGCD(ll a, ll b, ll& x, ll& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}

	ll x1, y1;
	ll g = extendedGCD(b, a % b, x1, y1);
	x = y1;
	y = x1 - (a / b) * y1;
	return g;
}

struct Point {
	ll curPos, moveDist;
	Point(ll pos, ll dist) : curPos(pos), moveDist(dist) {}
	Point() : curPos(0), moveDist(0) {}
};

int main()
{
	FAST;

	int n; cin >> n;
	vector<Point> arr(n);

	// 최소로 넘어야 하는 위치
	ll maxPos = 0;

	for (int i = 0; i < n; i++) {
		cin >> arr[i].curPos >> arr[i].moveDist;
		maxPos = max(maxPos, arr[i].curPos);
	}
	
	ll cur = arr[0].curPos;
	ll curDist = arr[0].moveDist;

	for (int i = 1; i < n; i++) {
		ll next = arr[i].curPos;
		ll nextDist = arr[i].moveDist;

		ll x, y;
		ll g = extendedGCD(curDist, nextDist, x, y);

		// 해가 없을 조건
		if ((next - cur) % g != 0) {
			cout << -1;
			return 0;
		}

		ll k = x * ((next - cur) / g);
		ll m = nextDist;
		k = (k % m + m) % m; // k를 양의 해로 바꿔준다

		ll newCur = cur + k * curDist;
		ll newDist = (curDist / g) * nextDist; // lcm
		
		cur = newCur % newDist;
		curDist = newDist;
	}

	// 답은 최소 위치를 넘어야 된다.
	if (cur < maxPos) {
		ll offset = maxPos - cur;
		ll steps = (offset + curDist - 1) / curDist;
		cur += steps * curDist;
	}

	cout << cur;


	return 0;
}