[백준] 6064번 카잉 달력

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

6064번: 카잉 달력

 

기준 : M = 10, N = 12 일때 year = 13 

1. <1, 1>
2. <2. 2>
3. <3, 3>
4. <4, 4>
5. <5, 5>
6. <6, 6>
7. <7, 7>
8. <8, 8>
9. <9, 9>
10. <10, 10>
11. <1, 11>
12. <2, 12>
13. <3. 1>

최대 범위는 M과 N의 최소공배수

이를 초과하면 유효하지 않음(-1 출력)

x 를 먼저 맞추고, y를 따라가게 계산

y는 M만큼 증가하고 N으로 나머지 연산을 하면 y값이 맞춰지게 됨

 

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            int M = sc.nextInt();
            int N = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();

            int lcm = M * N / gcd(M, N);
            // x를 연도로 먼저 맞춤
            int year = x;

            while (true) {
                // 연도가 최소공배수보다 큰 경우
                if (year > lcm) {
                	System.out.println(-1);
                	break;
                	// y의 기준인 N으로 나머지 연산을 하다가 y랑 같으면 해를 구할 수 있음
                } else if (((year % N) == 0 ? N : year % N) == y) {
                	System.out.println(year);
                	break;
                }

                year += M;
            }

        }

    }

    private static int gcd(int a, int b) {
        if (b == 0) {
        	return a;
        }
        return gcd(b, a % b);
    }
}