[SWEA] 3951 CRT

출처: [SWEA] SW 문제해결 심화 - 이산수학

 Input 

1

2

1 3

2 5

 

 Output 

#1 7

A ≡ bi mod(Ni) 관계에서 bi 와Ni 주어졌을 때, A를 만족하는 가장 작은 음이 아닌 정수 값을 찾으시오.

A는 A mod Ni = bi 가 되는 모든 값입니다.

ex) bi=2, Ni=3 이라면 A는 2, 5, 8, 11, 14 … 3k+2(k는 자연수)가 될 수 있다.

- Test Case 개수 T / 식의 개수 M / (M줄에 거쳐) bi 와 Ni 가 주어집니다.

 

▶ Chinese Remainder Theorem을 구현하는 문제입니다.

- 1 mod(3): 4 7 10 13 16 ...

- 2 mod(5): 2 7 12 17 22 ...

 

[예시 1]

x = 5 (mod 6) / x = 3 (mod 10) / x = 8 (mod 15)

① x = 5 (mod 6) → x = 6t + 5

② 6t + 5 ≡ 3 (mod 10) → 6t ≡ 8 (mod 10) → 3t ≡ 4 (mod 5) ▷ t ≡ 3 (mod 5)

     t = 5s + 3 → x = 6(5s + 3) + 5 → x = 30s + 23

③ 30s + 23 ≡ 8 (mod15) → 30s ≡ 0 (mod15) → 2s ≡ 0 (mod 1)

     → s = 0 (mod 1) → s = v

⑤ x = 30v + 23  → x ≡ 23 (mod 30)

 

[예시 2]

x ≡ 9 (mod 12) / x ≡ 0 (mod 9) / x ≡ 3 (mod 15) / x ≡ 13 (mod 16)

① x ≡ 9 (mod 12) → x = 12t + 9

② 12t + 9 ≡ 0 (mod 9) → 4t ≡ 0 (mod 3) → t ≡ 3s 

     → x = 12(3s) + 9 = 36s + 9

③ 36s + 9 ≡ 3 (mod 15) ▷ s ≡ 4 (mod 5) → s ≡ 5v + 4

    → x = 36(5v + 4) + 9 = 180v + 153

④ 180v + 153 ≡ 13 (mod 16) → v ≡ 1 (mod 4) → v ≡ 4u + 1

     → x = 180(4u+1) + 153 = 720u + 333 → x ≡ 333 (mod 720)  

 

 

구현

▶ X % number[i]    =  remainder[i]

① number[] 모든 원소의 곱한 결과를 구합니다.

② 각 수의 partial product of each number 부분곱을 구한 후,

    확장된 유클리드 알고리즘을 이용해서

    Modular multiplicative inverse of number[i] 구해서 결과를 더해줍니다.

③ 제일 작은 수를 구하기 위해서는 반환할 때, product 변수에 대한 나머지를 구합니다.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
         
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
             
            int M = Integer.parseInt(br.readLine());
            int remainder[] = new int[M];
            int number[] = new int[M];
             
            for(int i=0; i<M; i++) {
                st = new StringTokenizer(br.readLine());
                remainder[i] = Integer.parseInt(st.nextToken());
                number[i] = Integer.parseInt(st.nextToken());
            }
             
            System.out.println("#" + tc + " " + chineseRemainder(number, remainder));
        }
    }
 
    private static long chineseRemainder(int number[], int remainder[]) { 
        long product = 1; 
        for (int i = 0; i < number.length; i++) { 
            product *= number[i]; 
        }
       
        long result = 0; 
        for (int i = 0; i < number.length; i++) { 
            long partialProduct = product / number[i]; 
            result += remainder[i] * computeInverse(partialProduct, number[i]) * partialProduct; 
        } 
       
        return result % product; 
    } 
     
    private static long computeInverse(long a, int b) { 
        long m = b, t, q; 
        long x = 0, y = 1; 
       
        if (b == 1) return 0; 
       
        // 유클리드 알고리즘 적용
        while (a > 1) { 
            q = a / b; 
            t = b; 
             
            b = (int) (a % b);
            a = t; 
             
            t = x; 
            x = y - q * x; 
            y = t; 
        } 
         
        // 음수이면 양수로 만들기
        if (y < 0) y += m; 
       
        return y; 
    } 
}