총 M과 N의 최소공배수 만큼의 년도를 표시할 수 있으며, x:y가 해당 해를 M, N으로 나눈 나머지와 동일하다는 것을 알 수 있다.
(8) 2:8의 경우,
8을 M(6)으로 나눈 나머지인 2,
8을 N(9)으로 나눈 나머지인 8로 구성된다.
즉, x, y가 몇 번째 해(answer)를 나타내는지를 알기 위해서는, answer % M == x, answer % N == y 인 answer를 구하면 된다.
하지만, x, y가 3, 9 혹은 6, 9와 같이 M, N으로 나누었을 때, 나누어 떨어지면 문제가 발생하므로, 모든 x와 y에서 1을 뺀 값을 기준으로 해답을 구한 뒤, 1을 더해준다.
풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int t=0; t<T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// 최소공배수를 구하기 위해 최대공약수 구하기
int a = N;
int b = M;
int tmp = 0;
while (b != 0) {
tmp = b;
b = a % b;
a = tmp;
}
// 최소공배수
int lcm = M * N / a;
int answer = -1;
// 나머지가 0인 경우를 대비해 나머지가 x-1, y-1인 경우를 탐색
// x-1 부터 시작해 M씩 더해가며 해답을 도출
for (int i = x-1; i < lcm + 1; i += M) {
// (i%M) == x-1 이며(이미 충족), (i%N) == y-1인 i 탐색
if (i % N == y-1) {
answer = i;
break;
}
}
// 표현이 가능한 해면 + 1 해서 출력
// 아니면 -1 출력
sb.append(answer+1 !=0 ? answer+1 : -1).append('\n');
}
System.out.println(sb);
}
}
