BOJ 6064 - 카잉 달력

문제 링크

문제#

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 $M$과 $N$보다 작거나 같은 두 개의 자연수 $x$, $y$를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M이면 $x' = x + 1$이고, 그렇지 않으면 $x' = 1$이다. 같은 방식으로 만일 y < N이면 $y' = y + 1$이고, 그렇지 않으면 $y' = 1$이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, $M = 10$이고 $N = 12$라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 $M$, $N$, $x$, $y$가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력#

입력 데이터는 표준 입력을 사용한다. 입력은 $T$개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 $T$가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 $M$, $N$, $x$, $y$가 주어진다. $(1 \le M, N \le 40{,}000,\ 1 \le x \le M,\ 1 \le y \le N)$ 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력#

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해 정수 $k$를 한 줄에 출력한다. 여기서 $k$는 <x:y>가 $k$번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉 <x:y>가 유효하지 않은 표현이면 -1을 출력한다.

풀이#

카잉 달력은 k ≡ x (mod M)이고 k ≡ y (mod N)인 해를 찾는 문제로 볼 수 있다. 현재 코드는 x, x + M, x + 2M ...처럼 첫 번째 조건을 항상 만족하는 해만 순서대로 검사하면서, 그 해가 두 번째 조건까지 맞는지 확인한다.

검사는 달력의 마지막 해인 lcm(M, N)까지만 하면 충분하다. 그 안에서 맞는 해를 찾으면 바로 출력하고, 끝까지 못 찾으면 그런 해가 없는 것이므로 -1이 된다.

코드#

#include <iostream>
using namespace std;
 
int gcd(int m, int n) {
	int r = m % n;
 
	if (r == 0)
		return n;
	else
		return gcd(n, r);
}
 
int lcm(int m, int n) {
	return m * n / gcd(m, n);
}
 
void solve() {
	int t, m, n, x, y, i;
	cin >> t;
 
	while (t--) {
		cin >> m >> n >> x >> y;
		int limits = lcm(m, n);
 
		for (i = x; i <= limits; i += m) {
			int y_prime = (i % n == 0) ? n : i % n;
 
			if (y_prime == y) {
				cout << i << '\n';
				break;
			}
 
		}
 
		if (i > limits)
			cout << -1 << '\n';
	}
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: 한쪽 주기를 따라 후보를 건너뛰므로 테스트케이스당 $O(N / \gcd(M, N))$이다.
• 공간 복잡도: 추가 자료구조 없이 계산하므로 $O(1)$이다.

마무리#

카잉 달력은 k ≡ x (mod M)이고 k ≡ y (mod N)인 해를 찾는 문제로 볼 수 있다.