[백준/C++] 6064번

Cain Calendar

문제

It was recently revealed by the ICPC excavation team that the Inca Empire was established just after the Cain Empire which was a splendid civilization that flourished in South America. It is believed that the people in the Cain Empire used an interesting odd calendar. In their calendar, a year was represented by , where x and y are natural numbers which are less than or equal to M and N, respectively. The first year, that is, the beginning of the world is represented by <1:1>. The second year is represented by <2:2>. Let <x':y'>be the following year of . If x < M, x' = x + 1, otherwise x' = 1. Similarly, if y < N, y' = y + 1, otherwise y' = 1. The last year of their calendar is . It is said that there was a prophecy which states the world ends in the year .

For example, assume that M = 10 and N = 12. The first year is represented by <1:1>. The year <1:11> represents the 11th year, <3:1> represents the 13th year, and <10:12> represents the 60th year which is the last year.

Given four integers M, N, x, and y, write a program that computes the number k such that represents the kth year, where is the last year of the world in the Cain Calendar.

입력

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of a single line containing four integers M, N, x, and y (1 ≤ M,N ≤ 40 000, 1 ≤ x ≤ M, 1 ≤ y ≤ N), where is the last year of the world in the Cain Calendar.

출력

Your program is to write to standard output. Print exactly one line for each test case. The line should contain an integer k, where the kth year is represented by for x and y given in the input. If there doesn’t exist a year represented by , print -1.

예제 입력 1

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

예제 출력 1

33
-1
83

풀이

싹 다 돌면 시간초과 뜬다. 어차피 나머지만 이용하면 일정 수가 돌아오는 주기가 일정하니 건너뛰면서 순회하면 된다.

#include <iostream>
#include <vector>
using namespace std;

int LCM(int M, int N)
{
		int mul = M * N;
			while(N > 0) {
						int tmp = N;
								N = M % N;
										M = tmp;
											}
				return mul / M;
}

// 인덱스 구하는 루프문 하나 구하고 인덱스 구한 다음에는 M씩 점프. 그 점프하는 루프에서 y가 나머지로 나오거나 나누어떨어지는 경우를 찾으면 됨

int solution(int M, int N, int x, int y)
{
		int total = LCM(M, N);
			int index;
				
				for(index = 1; index <= total; ++index)
							if((index - 1) % M + 1 == x) break;
					
					for(int i = index; i <= total; i+= M)
								if((i - 1) % N + 1 == y) return  i;
						
						return -1;
}

int main()
{
		int C, M, N, x, y;
			cin >> C;

				while(C--) {
							cin >> M >> N >> x >> y;
									cout << solution(M, N, x, y) << endl;
										}

					return 0;
}