[BOJ] 6064. 카잉 달력

문제 원본 : https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        int m, n, x, y;
        StringBuilder builder = new StringBuilder();

        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            int g = gcd(m, n);
            int lcm = m * n / g;

            int ans = x;
            while (true) {
                if ((ans - y) % n == 0) {
                    builder.append(ans).append("\n");
                    break;
                } else if (ans > lcm) {
                    builder.append("-1\n");
                    break;
                }

                ans += m;
            }
        }

        bw.write(builder.toString());

        bw.close();
        br.close();
    }

    public static int gcd(int a, int b) {
        while (b > 0) {
            int r = a % b;
            a = b;
            b = r;
        }

        return a;
    }
}

• 아이디어 참고
• 한쪽을 고정시키고 반대쪽을 최댓값(M이나 N)으로 나머지 연산을 하면 쉽게 구할 수 있다.
• 마지막 해는 M과 N의 최소공배수에 해당한다.
• 유클리드 호제법을 이용해 최대공약수와 최소공배수를 구한다.