연립 선형 합동식

다음의 형태로 주어지는 문제이다
- x % m_1 = a_1, x % m_2 = a_2, …, x % m_n = a_n

중국인의 나머지 정리 (Chinese Remainder Theorem; CRT)

중국인의 나머지 정리는 m_i가 모두 서로소일 경우에 이 문제의 해가 법 m_1*m_2*…*m_n 에 대해 유일하게 존재한다는 정리이다.
- 서로소가 아니면 해가 존재하지 않을수도 있다.
보통은 그냥 연립 선형 합동식을 중국인의 나머지 정리라고 퉁쳐서 부르는 경우가 많은데, 사실 이 '정리'에는 그래서 저 해를 어떻게 구하는지에 대한 '알고리즘'은 포함되어있지 않다.
- 실제로 저 정리가 처음 등장한 중국 문헌에서는 증명이나 알고리즘은 없었다고 한다.
수학 문제를 풀때에는 '해의 존재성' 자체만으로도 매우 유용하게 사용되지만, PS에서 필요한 것은 실제로 해를 구하는 알고리즘이다

a_i가 모두 같은 값일때

이런 경우는 심플하다. x = k * lcm(m_1, m_2, …, m_n) + a_0이다

m_i가 모두 서로소일때

중국인의 나머지 정리에 따라서 해가 항상 존재한다.
실제로 연립 선형 합동식 문제가 주어졌을때, 그것을 풀기 위해서도 필요하지만 (퍼즐 문제 풀다보면 가끔 나온다), PS에서는 결과값이 매우 큰 계산식 f(x)를 M으로 나눈 나머지를 구하는 데에도 많이 사용된다. f(x)를 M으로 나눈 나머지는 계산하기 어렵지만, f(x)를 소수 p나 소수의 거듭제곱 p^e 로 나눈 나머지는 계산이 가능할 경우 (예를 들면 이항 계수 (Binomial Coefficient)), M을 소인수분해해서 M=p1^e1*p2^e2*… 으로 만들고, f(x) % p1^e1, f(x) % p2^e2, … 를 각각 계산하면, 그로부터 f(x) % M을 구할 수 있다.
또, 정말 매우 큰 수 N을, 미리 정해놓은 소수 p1,p2,p3…을 이용하여 (N%p1, N%p2, N%p3, …) 과 같이, 작은 수의 배열로 표현하는 활용법도 있다고 한다.

풀이

해를 구하는 방법은 어렵지 않게 유도 가능하다. 위키 참조.
공식은 $ x \equiv \sum^{n}_{i=1} M_i(M_i^{-1} mod\ m_i)a_{i} (mod\ M), $ (where $ M = m_1m_2m_3 ... m_n, M_i = M/m_i $)
n개의 m_i에 대해서 log(m_i)가 걸리는 모듈러 역원 계산이 필요하다. 그래서 O(n + sum_i(log(m_i))이다
- sum_i(log(m_i)) = log(m_1*m_2*…*m_n) = logM 이니까 O(n+logM)이라고 쓸수도 있고, 그냥 간단하게 하자면 O(nlogm) (m = max(m_i)) 로 쓸수도 있다. 모듈러 역원 계산을 미리 전처리해놓으면 q개의 쿼리에 대해서 총 처리 시간은 O(nq+logM) 에 처리가 가능하다.
PS와는 관계 없는 이야기이지만, 퍼즐 문제를 풀거나, 정수론 수업을 듣는 경우에, 이것을 손으로 계산할 경우에는 n이 3개만 돼도 꽤나 노가다가 필요하다..

코드

teflib.numtheory.linear_congruences

m_i가 서로소가 아닐 때

이때는 해가 존재하지 않을수도 있다. 해가 존재한다면 법 M = LCM(m_1, m_2, …, m_n) 에 대해서 유일하게 존재한다.

풀이

적은 갯수의 식을 손으로 계산할 때에는, 서로소가 아닌 m_i, m_j 쌍을 찾고 식을 나눠서 위의 방법을 적용하는 방법을 쓰기도 한다
- m_i = s*g, m_j = t*g 라면, x % s = a_i, x % t = a_j, x % g = a_i = a_j 이런식으로 식을 쪼개는 것
- 이렇게 쪼개서 만들어진 식들 간에 모순이 생기면 (x%s=a와 x%s=b가 동시에 생겼는데 a%s!=b%s 이면), 이 선형방정식은 해를 갖지 않는다.
그러나 그냥 일반적인 방법으로 두개의 식을 하나로 합칠수가 있고, 이것을 반복해서 최종 답을 구할수 있다. 컴퓨터로 짤때는 이게 더 편하다
- x≡a (mod m), x≡b (mod n) 을 만족하는 x를 찾으려면, 우선 확장 유클리드 알고리즘으로 mu+nv=gcd(m,n)=g이 되는 u,v를 구한다
- a≡b (mod g) 일때만 해가 존재하고, 그때의 해는 x ≡ (avn+bum)/g (mod lcm(m,n)) 으로 합칠수 있다.
  - 만약 해가 존재하는지 확인하기 위해서 l = (a-b)/g 을 이미 계산했다면, 아래 식은 x ≡ (a-l*u*m) (mod lcm(m,n)) 으로 좀더 간단히 바꿔서 계산할수도 있다
이 방법은 확장 유클리드 알고리즘을 n번 사용해야 한다. 확장 유클리드 알고리즘의 시간복잡도는 O(logm) 여기에서는 m이 lcm(m_1,…,m_i)가 될때까지 점점 커진다. 대충 O(nlogM) (M=lcm(m_1,…,m_i))으로 생각할 수 있다.
모듈러스가 모두 서로소인 경우에 비해서 시간복잡도가 조금 더 크지만, 큰 차이가 나는 것은 또 아니다.

코드

(기존에는 모듈러스가 서로소인 경우와 아닌 경우를 다른 함수로 구현했으나, 그냥 linear_congruences 함수 한개에서 모두 처리하기로 바꿨다.)
teflib.numtheory.linear_congruences

목차

연립 선형 합동식

중국인의 나머지 정리 (Chinese Remainder Theorem; CRT)

a_i가 모두 같은 값일때

m_i가 모두 서로소일때

풀이

코드

관련 문제

m_i가 서로소가 아닐 때

풀이

코드

관련 문제