[C++] 6064: 카잉 달력

6064번: 카잉 달력

풀이

중국인 어쩌고 모르겠어서 다른 방식으로 풀었다.

$k = m * d1 + x$ $⋅⋅⋅$ (1)
$k = n * d2 + y$ $⋅⋅⋅$ (2)

d1, d2를 0에서부터 1씩 늘려서 식(1)과 (2)가 같아질 때를 찾는다.
(1)이 크면 d2를 1 늘리고, (2)가 크면 d1을 1 늘린다.
마지막 해는 m * n 이므로, 그 너머로 가면 유효하지 않은 표현이다. 즉 d1이 n보다 커지거나, d2가 m보다 커지는 경우에는 -1을 출력한다.

코드

#include <iostream>
#define FOR(i, n) for(int i = 0; i < n; i++)
#define FOR1(i, n) for(int i = 1; i <= n; i++)
using namespace std;

int n;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	FOR(i, n) {
		int m, n, x, y;
		cin >> m >> n >> x >> y;

		int d1 = 0, d2 = 0;
		while (true) {
			if (m * d1 + x == n * d2 + y) {
				cout << m * d1 + x << '\n';
				break ;
			}
			if (d1 > n || d2 > m) {
				cout << -1 << '\n';
				break ;
			}
			if (m * d1 + x < n * d2 + y)
				++d1;
			else
				++d2;
		}
	}
	return (0);
}

중국인의 나머지 정리

양의 정수 $m_1, m_2, ... , m_n (n \ge2)$ 이 쌍마다 서로소일 때,
임의의 $c_1, c_2, ..., c_n$에 대하여

$x\equiv c_1(\text{mod } m_1)$
$x\equiv c_2(\text{mod } m_2)$
$...$
$x\equiv c_1(\text{mod } m_n)$

위 연립합동식은 유일한 $x\equiv u(\text{mod } m_1⋅ m_2⋅...\text{ }⋅m_n)$을 가진다.

Reference

https://dad-rock.tistory.com/738