백준 6064 : 카잉 달력

1. 문제 : https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

2. 문제 접근

• 해가 지날 수록 $x$와 $y$에 $1$을 더함.
• $x$와 $y$는 현재 해를 각각 $M$과 $N$으로 나눈 나머지임.
• 두 수의 최소 공배수를 주기로 $x$와 $y$가 반복됨.
• 완전 탐색으로 모든 수를 탐색할 경우 int 타입의 최댓값은 약 20억이므로 시간 초과.
• $x$, $y$ 중 하나를 기준으로 최소 공배수까지 탐색.

 

3. 문제 해결

1. $M$과 $N$의 최대 공약수를 활용하여 최소 공배수를 구함.

2. $x$를 기준으로 해를 $N$으로 나눈 나머지가 $y$와 같은지 판별.

3. 값을 찾은 경우 해당 해를 반환, 그렇지 않은 경우 $-1$을 반환

 

4. 코드

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
	if (b == 0) return a;

	return gcd(b, a % b);
}

int solution(int M, int N, int x, int y)
{
	int answer = -1;
	// Repeat with a period equal to the LCM of M and N
	int max = M * N / gcd(M, N);

	// x and y are the remainders when divided by M and N
	for (int i = x; i <= max; i += M)
	{
		int ty = i % N;

		// if the remainder is 0, the value needs to be fixed because the calendar starts from 1
		if (ty == 0) ty += N;
		if (ty == y)
		{
			answer = i;
			break;
		}
	}

	return answer;
}

int main()
{
	int T, M, N, x, y;
	
	cin >> T;
	
	for (int i = 0; i < T; i++)
	{
		cin >> M >> N >> x >> y;
		cout << solution(M, N, x, y) << endl;
	}
	
	return 0;
}