Euclidean Algorithm의 느낌으로 생각하면, ax+by=s를 만족하는 음이 아니고 서로소인 두 정수 x,y를 찾으면 된다.
(UPD: 사실 이 점을 증명하는 것도 trivial 한 것은 아니다. 머리를 좀 쓰긴 해야함)
일반적으로 ax+by=s를 푸는 것은 Extended Euclidean Algorithm을 알면 쉽게 구현 가능하다.
gcd(a,b)=1이 되도록 식을 reduce 시키고, 얻은 새로운 식을 ax+by=s라고 재정의하자.
이제 ax+by=1을 만족하는 정수 x,y를 Extended Euclidean Algorithm (Modular Inverse)으로 구할 수 있다.
위 식을 단순하게 s배 하기만 하면, ax+by=s인 정수 x,y를 하나 찾을 수 있다. 이를 x0,y0라 하자.
우리는 ax+by=s가 성립하면, 정수 k에 대해 x=x0+bk, y=y0−ak라고 쓸 수 있음을 안다.
이제 x0,y0를 적당히 이 방식대로 바꿔서, x0<b가 성립하도록 할 수 있다.
다시 x=x0+bk, y=y0−ak로 solution set을 parametrize하자.
x,y≥0이어야 하니, k≥0인 경우만 보면 된다는 것을 알 수 있다.
이제 목표는 k≥0, x0+bk≥0, y0−ak≥0, gcd(x0+bk,y0−ak)=1인 정수 k가 존재하는지 여부다.
꽤 어려운 문제처럼 보이지만, 알고리즘 문제를 푸는 입장에서 solution은 간단하다.
단순히 k에 대해서 iterate 하면서, 조건을 만족하는 k가 나오면 YES를 찍고, 아니면 NO를 찍으면 된다.
k≥0, x0+bk≥0, y0−ak≥0를 만족하는 정수 k의 개수는 10^18-scale까지 커질 수 있다는 것을 생각하자.
이 알고리즘이 시간 안에 답을 낸다는 사실은 (구현하면 0ms 뜬다) 수학적으로 전혀 자명하지 않다.
Claim: 문제 조건에서 gcd(x0+bk,y0−ak)=1을 만족하는 최소의 음이 아닌 정수 k는 최대 2^15이다.
이 Claim이 증명되면, 풀이가 시간 안에 도는 이유는 자명하다.
k에 대한 iteration이 최대 2^15번 돌기 때문에, 코드의 시간복잡도는 대강 O(2^15logs)정도가 된다.
이 정도의 시간복잡도/상수면, 코드가 0ms 안에 도는 것도 충분히 설명된다.
Claim 증명
자연수 D가 있어, 각 k=0,1,⋯D−1에 대해 gcd(x0+bk,y0−ak)≠1이라 하자.
최대공약수가 1이 아니라는 것은 공통 소인수가 있다는 것이다.
그러니 각 k=0,1,⋯,D−1에 대해 x0+bk와 y0−ak의 공통 소인수를 아무거나 하나 잡아서 이를 pk라 하자.
우선 s≡ax0+by0≡a(x0+bk)+b(y0−ak)≡0(modpk)이므로, pk|s를 얻는다.
즉, pk로 가능한 소수의 개수는 유한하다. (특히, s≤1018이므로, 최대 15개가 존재한다)
P=pi=pj인 두 정수 0≤i,j<D가 있다고 가정하자.
그러면 x0+bi≡x0+bj≡y0−ai≡y0−aj≡0(modP)가 성립한다.
이를 정리하면, P|b(i−j), P|a(i−j)가 성립한다. gcd(a,b)=1이므로, i≡j(modP)를 얻는다.
이 시점에서 상황을 정리해보자.
- s의 소인수는 최대 15개가 있다.
- 각 k=0,1,⋯D−1에 대해, 소수 pk는 s의 소인수다.
- s의 각 소인수 P에 대해서, P=pk인 index k의 수열은 공차가 P인 등차수열에 완전히 포함된다.
이 상황을 약간 다르게 해석해보자.
- s의 각 소인수 P에 대해서, P=pk인 index k의 수열은 공차가 P인 등차수열에 완전히 포함된다.
- s의 각 소인수 P에 대해서, P=pk인 index k의 수열을 포함하는 등차수열 {vP+Pn}n∈Z를 생각하자.
- 각 소인수에 대해서 얻은 등차수열의 합집합을 생각하면, 0,1,⋯,D−1을 전부 cover 한다.
- 즉, {0,1,2,⋯,D−1}⊆∪P|s,P is prime{vP+Pn}n∈Z이다.
그런데, 중국인의 나머지 정리의 느낌으로 생각하면, ∪P|s,P is prime{vP+Pn}n∈Z
는 절대로 정수 집합 전체가 될 수 없다.
이제 문제를 다음과 같은 느낌으로 바꾸어서 생각할 수 있다.
- 정수 전체를 cover 하지는 않는 등차수열이 k개가 있다.
- 이 등차수열들은 최대 몇 개의 연속한 자연수를 cover 할 수 있을까?
이 문제는 어느 정도 유명한 문제다. 개인적으로 아주 좋아하는 정리 중 하나를 소개한다.
Theorem: (Erdős, Crittenden, Vanden Eynden)
F는 k개의 등차수열 ai+diZ의 집합으로, (1≤i≤k) 1<d1<d2⋯<dk다.
만약 F가 연속한 2k개의 정수를 cover 한다면, F는 정수 전체를 cover 하는 집합이다.
Theorem 증명 (Taken From "Problems From The Book" pp. 152-153)
정수 x,x+1,⋯x+2k−1이 모두 F에 의해 cover 된다고 가정하자.
각 0≤t<2^k에 대해서, 적당한 1≤j≤k가 있어 x+t≡aj(mod dj)다.
이를 다르게 해석하면, 각 0≤t<2^k에 대해서 ∏j=1k(1−e2πidj(x+t−aj))=0라는 것이다. (동치조건이다)
이 식을 전개하면, ∑I⊂SαI⋅e(x+t)βI=0형태로 쓸 수 있음을 알 수 있다.
단, S={1,2,⋯k}이며, αI와 βI는 I,ai,di에만 영향을 받는 값이다. 정확하게 말하자면,
∏j=1k(1−e2πidj(x+t−aj))=∑I⊂S(−1)|I|⋅e−2πi∑j∈Iaj/dj⋅e2πi(x+t)∑j∈I1/dj이 성립한다. 이제 zI=eβI라고 두면, 각 0≤t<2^k에 대해서 ∑I⊂SαIzx+tI=0이다.
이제 un=∑I⊂SαIznI라고 하자. un=0인 것은, n이 F에 의해 cover 되는 것과 동치임을 정의상 알 수 있다.
식의 형태를 보면서 linear recurrence의 characteristic polynomial이 생각이 날 것이다.
다항식 ∏I⊂S(X−zI)=X2k+A2k−1X2k−1+⋯+A1X1+A0를 생각하자.
그러면 각 I⊂S에 대해 zn+2kI+A2k−1zn+2k−1I+⋯+A1zn+1I+A0znI=0이다.
이 식들을 적당히 선형결합하면, un+2k+A2k−1un+2k−1+⋯+A1un+1+A0un=0이다.
한편, 이미 ux=ux+1=⋯=ux+2k−1=0을 알고 있으니, 모든 n에 대해서 un=0임이 자명하다.
증명 과정에서는 A0≠0이라는 (자명한) 사실이 사용된다. 나머지는 전형적인 귀납법. 증명 끝.
이제 끝났다. 지금까지의 관찰을 합쳐서, D≤215임을 알 수 있다. 증명 끝.
참고
- rkm0959님 블로그
