Baekjoon 6064 카잉 달력

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

소스 결과 1988 KB / 52 ms

언어 C++ 17

출처 Baekjoon, ACM-ICPC 2013

분류 수학

 

설명

카잉 달력의 M, N 이 주어질 때 x : y 년이 몇 번째 해인지 계산하자

 

일전에 비슷한 문제로 현재 문제의 입력과 출력이 반대였던 문제를 푼 적이 있는 것 같다.

이번 문제를 풀기 위해서는 먼저 최소 공배수가 필요하다.

최소 공배수를 구하기 위해서는 최대 공약수가 필요하다. 유클리드 호제법을 이용해 최대 공약수를 구한 뒤, 최소 공배수를 구하면 된다.

 

처음에 이 문제의 최대 연월이 4만인 줄 알고, 최소 공배수가 4만이 넘어가는 경우 4만까지만 루프를 돌려 일일이 구하는 문제인 줄 알았으나 아니었다. 최대 경우의 수가 4만이 아니라 N, M의 값이 4만이었기에 최소 공배수는 1억대까지 갈 수 있었다.

 

문제를 해결하기 위한 방법으로는 x를 기준으로 하여 각 경우에 대해서 입력된 값과 일치하는 y가 존재하는지 찾으면 된다. y를 기준으로 x를 찾는 방법도 가능하다.

 

알고리즘

1. 최대 공약수를 구하여 최소 공배수를 구한다.

2. x를 기준으로 삼아 N의 배수 + x로부터 y를 구한 뒤, 입력된 y랑 일치하는지 탐색한다.

3. 일치하는 경우가 존재하면 N의 배수 + x를 출력한다.

4. 입력된 경우 중 경우가 없으면 -1을 출력한다.

 

소스코드

#include <iostream>

using namespace std;

int cal_gcb(int a, int b) {

	if (a > b)
	{
		if (a % b)
			return cal_gcb(b, (a % b));
		else
			return b;
	}
	else
	{
		if (b % a)
			return cal_gcb(a, (b % a));
		return a;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int tcc;

	cin >> tcc;

	while (tcc--) {
		int n, m, x, y;

		cin >> m >> n >> x >> y;

		int gcb = cal_gcb(m, n);
		int lcm = (m / gcb) * (n / gcb) * gcb;
		int res = -1;

		int leftDiff = x - 1;
		int rightDiff = y - 1;

		for (int i = 0; (m * i) < lcm; i++)
		{
			int mulX = m * i;
			int cur = mulX + leftDiff + 1;
			int right = (cur - 1) % n + 1;

			if (right == y)
				res = cur;
		}

		cout << res << '\n';
	}

	return 0;
}