백준 6064번(Java)

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);

    }
}