중국인의 나머지 정리

나머지를 사용하여 값을 찾을 때 사용하는 알고리즘

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

---

알고리즘

x = 2 (mod 5)
x = 2 (mod 7)
이 처럼 각 서로수로 나머지가 주어져 있을 때, x의 값을 구하는 방법은 간단하게
x = 2 (mod 5 x 7)로 구할 수 있다. 이 때는 35가 된다.
이러한 경우를 아주 간단한 나머지 정리라고 할 수 있다.

위의 문제를 풀때는 x, y에 각각 -1을 해주자.
만일 m과 x가 같을 경우 나머지가 0이 오는 것을 방지하기 위해서,
각각 -1을 해주고 마지막에 1을 더하여 계산하자.

자바 소스 코드

import java.util.Scanner;

public class Main {
    public static int calcGCD(int m, int n) {
        int r = m % n;
        while (r != 0) {
            m = n;
            n = r;
            r = m % n;
        }
        return n;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        while (t-- > 0) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            int x = sc.nextInt() - 1; // -1을 해주고
            int y = sc.nextInt() - 1;

            int lcm = m * n / calcGCD(m, n);

            int answer = -1;

            for (int i = x; i <= lcm; i += m) { // 최대값이 최소공배수이기 때문
                if (i % n == y) {
                    answer = i + 1;  // 답에 1을 더하여 출력
                    break;
                }
            }
            System.out.println(answer);
        }
    }
}