백준 6064번: 카잉 달력

문제 출처: https://www.acmicpc.net/problem/6064

문제 풀이 참고 출처: http://mygumi.tistory.com/325

그냥 풀면 시간초과가 난다. 

x를 먼저 맞추고, y만을 신경쓴다.

그렇게 되면 y는 M만큼 증가하고, y를 N으로 나머지 연산을 하면, y의 값을 알 수 있다. 

마지막 해는 최소공배수이다. M=10, N=12일 때 10과 12의 최소공배수는 60이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        StringBuilder builder = new StringBuilder();
        
        for(int n=0 ; n<T ; n++){
            String[] input = reader.readLine().split(" ");
            int M = Integer.parseInt(input[0]);
            int N = Integer.parseInt(input[1]);
            int x = Integer.parseInt(input[2]);
            int y = Integer.parseInt(input[3]);
            int count = x, j = x, lcm = lcm(M, N); // x를 먼저 맞춘다. 
            
            for(int i=0 ; i<lcm/M ; i++){
                int tempY = j % N == 0 ? N : j % N; // y를 N으로 나머지 연산
                
                if (tempY == y)
                    break;
                
                count += M;
                j = tempY + M;
            }
            count = (count > lcm) ? -1 : count; // count가 마지막 해보다 크면 -1
        
            builder.append(count).append("\n");
        }
        
        System.out.println(builder);
    }
    
    public static int lcm(int num1, int num2) { // 최소공배수 구하기
        int a = num1, b = num2;
        
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        
        return num1 * num2 / a;
    }
}