[BOJ] 백준 6064 카잉 달력

[문제]

https://www.acmicpc.net/problem/6064

 

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	int t = Integer.parseInt(br.readLine());
    	point:
    	while(t-->0) {
    		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());
    		if(m==x) x=0;
    		if(n==y) y=0;
    		int lcm = LCM(m,n);
    		for(int i=x;i<=lcm;i+=m) {
    			if(i==0) continue;
    			if(i%m==x && i%n==y) {
        			System.out.println(i);
        			continue point;
        		}
    		}
    		System.out.println(-1);
    	}
    }
    private static int LCM(int m,int n) {
    	return m / GCD(m,n) * n;
    }
    private static int GCD(int m,int n) {
    	if(n==0) return m;
    	return GCD(n,m%n);
    }
}