백준 6064번 카잉 달력 (java)

[Silver I] 카잉 달력 - 6064

문제 링크

성능 요약

메모리: 18920 KB, 시간: 320 ms

분류

브루트포스 알고리즘, 중국인의 나머지 정리, 수학, 정수론

제출 일자

2024년 12월 20일 17:32:08

문제 설명

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, 이 카잉 달력의 마지막 해라고 하면 는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 가 k번째 해를 나타내는 것을 의미한다. 만일 에 의해 표현되는 해가 없다면, 즉, 가 유효하지 않은 표현이면, -1을 출력한다.

예제 입력 1 

3
10 12 3 9
10 12 7 2
13 11 5 6

예제 출력 1 

33
-1
83

풀이

시간 초과를 피하기 힘든 문제다.

 

최소 공배수를 구한 후, 최소 공배수까지 1씩 더하며

 

i % M == x && i % N == y 를 만족하는 i를 찾으려 했다.

 

우선 i == M 일 경우 나머지가 0이 나오기 때문에 이를 대비해서 (i-x) % M == 0 과 같은 식으로 변경해주었다.

 

그러나 시간 초과가 발생했고, 시간 초과를 피하기 위해 1씩 더하는 방식 말고 다른 방식을 찾아보았다.

 

i % M == x 라는 말은 x에서 시작해서 M 만큼 더하면서 올라가면 항상 만족한다는 의미와 같다.

 

즉 x에서 시작해서 M씩 더하면서 올라가고 (i - N) == y를 만족하는 경우만 찾는 방식으로 풀 수 있다는 말이다.

 

위와 같은 방식으로 코드를 변경했더니 시간 초과를 피할 수 있었다.

 

코드

public class Main {
    static List<Integer> remainder = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for(int  i = 0;i<T;i++){
            remainder = new ArrayList<>();
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            int to = least_multiple(a,b);

            int flag = 0;

            for(int j=x;j<=to;j+=a){
                if((j-y) % b == 0){
                    System.out.println(j);
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                System.out.println(-1);
            }
        }
    }

    public static int least_multiple(int a, int b){
        int min = Math.min(a,b);

        for(int i=2;i<=min;i++){
            if(a%i==0 && b%i==0){
                remainder.add(i);
                a /= i;
                b /= i;
                i = 2;
            }
        }
        int result = a * b;
        for (Integer i : remainder) {
            result *= i;
        }
        return result;
    }
}