[백준 / C++] 6064번: 카잉 달력

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

난이도: solved.ac 실버 1

 

 

중국인의 나머지 정리? 를 이용해서 푸는 거라던데, 유클리드 호제법도 잘 모르는 나는 그냥 내 식대로 풀어봤다.

<x, y>를 만들기 위해 먼저 <x, x>부터 시작해서 두 번째 자리에 있는 x를 y로 만드는 것을 목표로 했다.

 

예를 들어 예제 입력 1의 첫 번째 케이스처럼 m = 10, n = 12, x = 3, y = 9라면,

일단 <3, 3>부터 시작해서 앞자리가 3인 다음 경우를 생각해 보면 <3, 1>이 된다. 그 다음 앞자리가 3인 경우는 <3, 11>가 된다. 그 다음은 <3, 9>로 우리가 원하는 <3, 9>가 만들어진다.

 

예제 입력 1 두 번째 케이스인 m = 10, n = 12, x = 7, y = 2인 경우에는 어떨까?

우선 똑같이 <7, 7>부터 시작한다. <7, 7> → <7, 5> → <7, 3> → <7, 1> → <7, 11> → <7, 9> → <7, 7> → <7, 5> → ... 처럼 <7, 2>를 찾지 못하고 <7, 7>로 다시 돌아와 반복된다.

 

위처럼 다시 돌아와서 위의 과정이 무한히 반복되는 경우를 탈출하기 위해 해당 수에 방문했는지 체크하는 배열을 만들어 파악해 주었다.

 

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	int m, n, x, y, T;
	cin >> T;
	while (T--) {
		cin >> m >> n >> x >> y;
		int max = m;
		if (n > m)
			max = n;
		
		int* arr = new int[max + 1]{};

		// x를 y로 만들기
		int flag = 0, ans = x;
		arr[x] = 1;

		x = x % n;
		if (!x)
			x = n;

		while (x != y) {
			x = (x + m) % n;
			if (!x)
				x = n;
			ans += m;
			if (arr[x]) {
				flag = 1;
				break;
			}
			arr[x] = 1;
		}

		if (flag)
			cout << -1 << endl;
		else
			cout << ans << endl;
		delete[] arr;
	}
}