스포 방지선
___________________________________________________________________________________________________________
___________________________________________________________________________________________________________
풀이
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의 개수는 1018-scale까지 커질 수 있다는 것을 생각하자.
이 알고리즘이 시간 안에 답을 낸다는 사실은 (구현하면 0ms 뜬다) 수학적으로 전혀 자명하지 않다.
1년 반 전에 이 문제를 풀었을 때 이 점은 개인적으로 숙제로 남아 있었다.
오늘 이 풀이가 시간 안에 도는 이유를 아는 분에게 질문 받아서, 고민을 하는 시간을 가져 해답을 찾았다.
사실 이 블로그를 쓰는 이유도 풀이를 쓰는 것보단 이 해답을 기록하기 위한 것이다.
Claim: 문제 조건에서 gcd(x0+bk,y0−ak)=1을 만족하는 최소의 음이 아닌 정수 k는 최대 215이다.
이 Claim이 증명되면, 풀이가 시간 안에 도는 이유는 자명하다.
k에 대한 iteration이 최대 215번 돌기 때문에, 코드의 시간복잡도는 대강 O(215logs) 정도가 된다.
이 정도의 시간복잡도/상수면, 코드가 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 \equiv ax_0 + by_0 \equiv a(x_0+bk)+b(y_0-ak) \equiv 0 \pmod{p_k}이므로, p_k|s를 얻는다.
즉, p_k로 가능한 소수의 개수는 유한하다. (특히, s \le 10^{18}이므로, 최대 15개가 존재한다)
P = p_i = p_j인 두 정수 0 \le i, j < D가 있다고 가정하자.
그러면 x_0 + bi \equiv x_0 + bj \equiv y_0 - ai \equiv y_0 - aj \equiv 0 \pmod{P}가 성립한다.
이를 정리하면, P|b(i-j), P|a(i-j)가 성립한다. \text{gcd}(a,b)=1이므로, i \equiv j \pmod{P}를 얻는다.
이 시점에서 상황을 정리해보자.
- s의 소인수는 최대 15개가 있다.
- 각 k=0, 1, \cdots D-1에 대해, 소수 p_k는 s의 소인수다.
- s의 각 소인수 P에 대해서, P = p_k인 index k의 수열은 공차가 P인 등차수열에 완전히 포함된다.
이 상황을 약간 다르게 해석해보자.
- s의 각 소인수 P에 대해서, P = p_k인 index k의 수열은 공차가 P인 등차수열에 완전히 포함된다.
- s의 각 소인수 P에 대해서, P = p_k인 index k의 수열을 포함하는 등차수열 \{v_P + Pn\}_{n \in \mathbb{Z}}를 생각하자.
- 각 소인수에 대해서 얻은 등차수열의 합집합을 생각하면, 0, 1, \cdots , D-1을 전부 cover 한다.
- 즉, \{0, 1, 2, \cdots , D-1\} \subseteq \cup_{P|s, P \text{ is prime}} \{v_P + Pn\}_{n \in \mathbb{Z}} 이다.
그런데, 중국인의 나머지 정리의 느낌으로 생각하면, \cup_{P|s, P \text{ is prime}} \{v_P + Pn\}_{n \in \mathbb{Z}} 는 절대로 정수 집합 전체가 될 수 없다.
이제 문제를 다음과 같은 느낌으로 바꾸어서 생각할 수 있다.
- 정수 전체를 cover 하지는 않는 등차수열이 k개가 있다.
- 이 등차수열들은 최대 몇 개의 연속한 자연수를 cover 할 수 있을까?
이 문제는 어느 정도 유명한 문제다. 개인적으로 아주 좋아하는 정리 중 하나를 소개한다.
Theorem: (Erdős, Crittenden, Vanden Eynden)
F는 k개의 등차수열 a_i + d_i \mathbb{Z}의 집합으로, (1 \le i \le k) 1 < d_1 < d_2 \cdots < d_k다.
만약 F가 연속한 2^k개의 정수를 cover 한다면, F는 정수 전체를 cover 하는 집합이다.
Theorem 증명 (Taken From "Problems From The Book" pp. 152-153)
정수 x, x+1, \cdots x+2^k-1이 모두 F에 의해 cover 된다고 가정하자.
각 0 \le t <2^k에 대해서, 적당한 1 \le j \le k가 있어 x+t \equiv a_j \pmod{d_j}다.
이를 다르게 해석하면, 각 0 \le t < 2^k에 대해서 \displaystyle \prod_{j=1}^k \left(1 - e^{\frac{2\pi i}{d_j} ( x+t-a_j)} \right) = 0라는 것이다. (동치조건이다)
이 식을 전개하면, \sum_{I \subset S} \alpha_I \cdot e^{(x+t) \beta_I} = 0 형태로 쓸 수 있음을 알 수 있다.
단, S = \{1, 2, \cdots k\}이며, \alpha_I와 \beta_I는 I, a_i, d_i에만 영향을 받는 값이다. 정확하게 말하자면, \prod_{j=1}^k \left(1- e^{\frac{2\pi i}{d_j}(x+t-a_j)} \right) = \sum_{I \subset S} (-1)^{|I|} \cdot e^{-2\pi i \sum_{j \in I} a_j/d_j} \cdot e^{2\pi i (x+t) \sum_{j \in I} 1/d_j} 이 성립한다. 이제 z_I = e^{\beta_I}라고 두면, 각 0 \le t < 2^k에 대해서 \sum_{I \subset S} \alpha_I z^{x+t}_I = 0이다.
이제 u_n = \sum_{I \subset S} \alpha_I z^n_I라고 하자. u_n = 0인 것은, n이 F에 의해 cover 되는 것과 동치임을 정의상 알 수 있다.
식의 형태를 보면서 linear recurrence의 characteristic polynomial이 생각이 날 것이다.
다항식 \displaystyle \prod_{I \subset S} (X-z_I) = X^{2^k} + A_{2^k-1} X^{2^k-1} + \cdots + A_1 X^1 + A_0를 생각하자.
그러면 각 I \subset S에 대해 z^{n+2^k}_I + A_{2^k-1} z^{n+2^k-1}_I + \cdots + A_1 z^{n+1}_I + A_0 z^n_I = 0이다.
이 식들을 적당히 선형결합하면, u_{n+2^k} + A_{2^k-1} u_{n+2^k-1} + \cdots + A_1 u_{n+1} + A_0 u_n = 0이다.
한편, 이미 u_x = u_{x+1} = \cdots = u_{x+2^k-1} = 0을 알고 있으니, 모든 n에 대해서 u_n = 0임이 자명하다.
증명 과정에서는 A_0 \neq 0이라는 (자명한) 사실이 사용된다. 나머지는 전형적인 귀납법. 증명 끝.
이제 끝났다. 지금까지의 관찰을 합쳐서, D \le 2^{15}임을 알 수 있다. 증명 끝.
Note. 관련된 문제인 RMM 2010 Problem 1을 참고하면 도움이 될 것 같다. 출제자는 Dan Schwarz.
'PS > 수학 계열 PS' 카테고리의 다른 글
| Project Euler 350문제 (0) | 2019.12.02 |
|---|---|
| Project Euler 691 (1) | 2019.12.01 |
| Project Euler 300문제 (0) | 2019.11.23 |
| 9월초 수학 PS 일지 (4) | 2019.09.11 |
| 7-8월의 수학 PS 일지 (3) | 2019.08.28 |
