백준 6064 - 카잉 달력

문제 번호: 6064

문제 제목: 카잉 달력

문제 주소: https://www.acmicpc.net/problem/6064

문제 내용

아래에 기술된 카잉 달력의 규칙에 따라 입력된 값이 몇 번째 해인지 출력한다.
유효하지 않은 값일 경우 -1을 출력한다.
 - 달력은 M : N으로 표기한다.
 - 한 해가 지나가면 M과 N은 각각 1씩 증가한다.
 - 현재 앞의 숫자가 M일 경우 다음 해의 M은 1이다.
 - 현재 뒤의 숫자가 N일 경우 다음 해의 N은 1이다.

테스트 케이스

3 10 12 3 9 10 12 7 2 13 11 5 6

33 -1 83

문제 풀이

1. 결과 값을 저장할 변수를 -1로 초기화 한다.
2. 종말의 날인 M : N은 M과 N의 최소 공배수인 해와 동일하다. 반복문은 이 범위 내에서만 돌리면 된다.
3. M * i + x를 N으로 나눈 나머지와 y를 N으로 나눈 나머지가 동일할 경우 x : y인 해가 존재하는게 된다.
   이 경우 M * i + x를 결과 값 변수에 대입하고 반복문을 break; 한다.
4. 결과 값을 출력한다.

풀이 코드

#include <iostream>
using namespace std;

int getGcd(int a, int b)
{
	while (b != 0)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int getLcm(int a, int b)
{
	return a * b / getGcd(a, b);
}

void BAEKJOON_6064()
{
	int T;
	cin >> T;

	int M;
	int N;
	int x;
	int y;

	while(T--)
	{
		cin >> M >> N >> x >> y;
		int result = -1;
		int endDate = getLcm(M, N);
		for (int i = 0; x + M * i <= endDate; i++)
		{
			if ((x + M * i) % N == y % N)
			{
				result = M * i + x;
				break;
			}
		}
		cout << result << endl;
	}
	return;
}