개요
이 포스팅에서는 지난번에 다룬 CRT에 이어, 서로소가 아닌 법들에 대한 일반적인 연립 합동식의 풀이를 다룬다.
연립 합동식의 풀이
이론 상 연립 합동식의 풀이를 할 때는, 합동식의 법들이 쌍마다 서로소인 경우에 중국인의 나머지 정리를 이용하여 문제를 해결할 수 있다. 하지만, 쌍마다 서로소임을 확인하는 과정은 실제로는 상당한 시간을 소모하며 (모든 쌍을 조사하므로 적어도 $O(n^2)$ 의 시간이 소요될 것이다.), 따라서 좀 더 간단하고 일반적인 풀이법을 소개하려고 한다.
2개의 연립 합동식의 풀이
지난 포스팅을 읽었다면 합동식을 푼다는 것은 그것과 동치인 부정 방정식의 해를 구하는 과정이란 점을 알 것이다. 따라서 아래와 같은 문제를 생각해보자.
다음 연립 합동식을 풀어라. 이때 2개의 법은 서로소임이 보장되지 않는다.
\[x\equiv{k_1}\pmod{m_1}\] \[x\equiv{k_2}\pmod{m_2}\]
풀이의 핵심은 각각의 합동식과 동치인 부정 방정식으로 치환하는 것이다. 따라서 아래와 같은 과정으로 문제를 해결할 수 있다.
각각의 식은 $x+{m_1}{y_1}=k_1$ 와 $x+{m_2}{y_2}=k_2$ 으로 치환이 가능하다.
\[{y_1}={ { {k_2}-{k_1} }\over{d} }\times{Y_1}+{ {m_2}\over{d} }t \ \ (t\in{\mathbb{Z}} )\]
즉, ${m_1}{y_1}-{m_2}{y_2}={k_1}-{k_2}$ 를 풀면 되고, $d=\gcd(m_1,m_2)$ 일 때, 해는 아래와 같다.$Y_1$ 은 확장 유클리드 알고리즘을 이용하여 구한 ${m_1}{y_1}-{m_2}{y_2}=d$ 에서 $y_1$ 의 특이해이다.
\[x={k_1}-{ { {k_2}-{k_1} }\over{d} }\times{m_1}{Y_1}-{ { {m_1}{m_2} }\over{d} }t\] \[x\equiv{k_1}-{ { {k_2}-{k_1} }\over{d} }\times{m_1}{Y_1}\pmod{ { {m_1}{m_2}\over{d} } }\]
다시 첫번째 식으로 돌아와서 $x$에 위에서 구한 $y_1$ 값을 대입하면,
즉, 2개의 합동식이 이제 1개의 합동식으로 바뀌었다. 또한 위의 과정에서 ${k_2}-{k_1}$ 이 $d$ 의 배수가 아니라면, 자명히 해는 존재하지 않는다.
$n$ 개의 합동식이 주어진 경우
위의 결론을 얻었으므로, $n$ 개의 합동식이라고 특별할 이유가 없다. 단순히 1번째와 2번째 식을 연립하여 결과물을 얻고, 그 결과물과 3번째 식을 연립하여 풀고, … 이 과정을 반복하면 전체 연립 합동식이 풀리게 된다. 자명히 중간 과정에서 해가 존재하지 않는 결론이 나온다면 전체 연립 합동식의 해 역시 존재하지 않을 것이다.
이제 시간 복잡도를 분석해보자. 과정은 굉장히 단순하고, 총 $n$ 개의 연립 합동식을 풀 때, 2개의 합동식을 합치는 횟수는 $O(n)$ 이다. 또한 각각을 합칠 때 마다, 확장 유클리드 알고리즘이 1번씩 사용되므로 $O(\log{M})$ 의 시간이 걸린다. 이때 $M=\operatorname{lcm}(m_1,m_2,\cdots{},m_n)$ 이다. 따라서 전체 시간 복잡도는 $O(n\log{M})$ 이다.
본 방식의 문제점
지금까지 일반적인 경우의 연립 합동식 풀이법을 배웠다. 본 풀이법은 이론 상 오류는 없지만, 실제 구현에서 주의를 기울여야 할 부분이 있다. 바로 오버플로우를 잘 관리해야 하는데, 잘 보면 확장 유클리드 알고리즘을 사용하여 특이해를 구할 때가 가장 위험하단 것을 알 수 있다. 따라서 구현시 파이썬이나 자바의 BigInteger 등을 사용하여 잘 구현을 해야할 것이다. 하지만 대회에 이런 문제가 출제된다면, 아마도 C++로는 풀 수 없도록 테스트 케이스를 구성했을 가능성은 적다고 생각하기에 이 내용을 외우기보단 이해해놓고 잘 사용하도록 하자.