티스토리 뷰
1) 중국인의 나머지 정리
중국인의 나머지 정리는 PS를 하면서 간혹 등장한다. 답이 큰 경우 일반적으로 $M$으로 나눈 나머지를 출력하라고 한다. 하지만 이 $M$이 고정되어 있지 않고, 입력으로 $k$가지가 주어진다고 할 경우 $k$ 개 경우에 대해서 매번 다 계산하면 오래걸린다. 이럴 때 필요한 것이 바로 중국인의 나머지 정리다.
정리)
서로소인 $k$개의 자연수 $n_1, n_2, \dots, n_k$와 임의의 정수 $a_1, a_2, \dots, a_k$가 있을 때, 임의의 $i (1 \leq i \leq k)$에 대해 $x \equiv a_i (\mod n_i)$ 로 표현되는 변수 $x$의 연립 합동 방정식에 대해, 이 방정식이 성립하는 해 $x = a$가 항상 존재하며, $n_1 n_2 \dots n_k$ 모듈로 안에서 유일하다. 즉, 이 방정식의 해는 $x \equiv a (\mod n_1 n_2 \dots n_k)$로 표현 가능하다.
증명과 계산 방법)
$N = n_1 n_2 \dots n_k$ 라고 하자. $N / n_i$는 $n_i$와 서로소이기 때문에, $r_i n_i + s_i(N / n_i) = 1$인 정수 $r_i, s_i$가 항상 존재한다. (확장 유클리드) 여기에서, $e_i = s_i(N / n_i)$라고 하면 아래와 같은 등식이 성립한다.
$e_i \equiv 1 (\mod n_i)$
$e_i \equiv 0 (\mod n_j) (i \not= j)$
여기에서 $a = \sum\limits^{k}_{i=1}{a_i e_i}$라고 하면, 임의의 $i$에 대해 $a \equiv a_i (\mod n_i)$가 성립한다. 즉, $a$는 우리가 구하고자 하는 해 중 하나이다.
이제 $a$의 $N$ 모듈로 안에서 유일성을 증명하기 위해, 두 해 $x, y$가 존재한다고 가정하자. 그러면 $x \equiv a_i, y \equiv a_i (\mod n_i)$ 이므로 $x - y$는 모든 $n_i$의 배수이고, 따라서 $N$의 배수이다. 즉, $x \equiv y (\mod N)$이므로 해가 유일하다는 것이 증명된다.
2) 일반적인 상황에서 연립 합동 방정식의 해 구하기
변수 $x$에 대한 연립 합동 방정식이 두 개 있다고 하자.
$$x \equiv a_1 \mod m_1\\x \equiv a_2 \mod m_2$$
이 방정식의 해 $x$가 존재한다면, 다음과 같다. $x = k_1m_1 + a_1 = k_2m_2 + a_2$. 이 식은 다음과 같이 정리할 수 있다.
$$k_1m_1 - k_2m_2 = a_2-a_1$$
$m_1$과 $m_2$의 최대공약수를 $g$라고 하자. 만약 두 수가 서로소라면 $g=1$이다. 위 식을 만족하는 정수 $k_1$과 $k_2$가 존재하기 위한 필요충분조건은 $a_2-a_1$가 $g$의 배수여야 한다. (확장 유클리드 알고리즘)
$k_1$과 $k_2$의 정수해는 여러 쌍이 있을 수 있다. 그중 $k_1$의 임의의 해를 $k_0$라 하자. 확장 유클리드 알고리즘을 통해 $k_0$를 구할 수 있다.
$k_1$의 일반해는 다음과 같이 표현할 수 있다.
$$k_1 = k_0 + l\frac{m_2}{g}$$
즉, $k_1$의 정수해는 $\text{mod} \frac{m_2}{g}$에서 유일하다. 이를 $x = k_1m_1 + a_1$에 대입하면 다음과 같다.
$$x = k_0m_1+l\frac{m_1m_2}{g} + a_1$$
즉, $x$의 해가 $\text{mod} \frac{m_1m_2}{g}$에서 유일하며, 그 해는 다음과 같다.
$$x \equiv k_0m_1 + a_1 \mod \frac{m_1m_2}{g}$$
3) 확장 유클리드 알고리즘
확장 유클리드 알고리즘은 모듈로 안에서 곱셈에 대한 역원을 구할 때나, 앞에서 설명한 중국인의 나머지 정리에서 해를 구할 때 사용된다.
이에 대해 간략하게 설명하면 임의의 정수 $a, b$에 대하여 $\gcd(a,b) = ax + by$을 만족하는 $x, y$가 항상 존재한다는 것이다. 이 때, $x$와 $y$를 구할 수 있다.
곱셈의 역원)
$M$ 모듈로 안에서 $n$의 곱셈에 대한 역원이란, $ns \equiv 1 (\mod M)$을 만족하는 $s$를 의미하며, $n$과 $M$이 서로소일 때 존재한다. 확장 유클리드 알고리즘에서의 식에 $n, M, s$를 대입하면 $\gcd(n,M) = xM + ns$ 를 만족하는 $x, s$가 존재하며, $\gcd(n,M) = 1$일 때 $s$는 $M$ 모듈로 안에서 $n$의 곱셈에 대한 역원이 된다.
구하는 방법)
'공부' 카테고리의 다른 글
Suffix Array와 LCP (14) | 2014.08.14 |
---|---|
Manacher's Algorithm (0) | 2014.08.13 |
고속 푸리에 변환 (Fast Fourier Theorem, FFT) (9) | 2014.07.25 |
포함-배제의 원리 (0) | 2014.07.20 |
Nim game (6) | 2013.07.29 |
- Total
- Today
- Yesterday
- majority
- IOI2013
- moore
- USACO
- z-trening
- Algorithm
- Boyer-Moore Majority Vote Algorithm
- BOI 2009
- IOI2012
- BOI
- Dynamic Pramming
- Splay Tree
- Dijkstra
- Segment tree
- BOI 2001
- vote
- dynamic programming
- Divide & Conquer
- Knuth Optimization
- optimization
- Greedy Method
- IOI2011
- ioi
- IOI2014
- Boyer
- Tree
- TRIE
- Parametric Search
- idea
- HackerRank
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |