BOJ #9267 - A + B (SEERC 2013)

문제

스포 방지선

___________________________________________________________________________________________________________

___________________________________________________________________________________________________________

풀이

Euclidean Algorithm의 느낌으로 생각하면, \(ax+by=s\)를 만족하는 음이 아니고 서로소인 두 정수 \(x, y\)를 찾으면 된다.

(UPD: 사실 이 점을 증명하는 것도 trivial 한 것은 아니다. 머리를 좀 쓰긴 해야함) 

일반적으로 \(ax+by=s\)를 푸는 것은 Extended Euclidean Algorithm을 알면 쉽게 구현 가능하다. 

\(\text{gcd}(a, b)=1\)이 되도록 식을 reduce 시키고, 얻은 새로운 식을 \(ax+by=s\)라고 재정의하자. 

이제 \(ax+by=1\)을 만족하는 정수 \(x, y\)를 Extended Euclidean Algorithm (Modular Inverse)으로 구할 수 있다. 

위 식을 단순하게 \(s\)배 하기만 하면, \(ax+by=s\)인 정수 \(x, y\)를 하나 찾을 수 있다. 이를 \(x_0, y_0\)라 하자.

우리는 \(ax + by=s\)가 성립하면, 정수 \(k\)에 대해 \(x = x_0 + bk\), \(y = y_0 - ak\)라고 쓸 수 있음을 안다. 

이제 \(x_0, y_0\)를 적당히 이 방식대로 바꿔서, \(x_0 < b\)가 성립하도록 할 수 있다. 

다시 \(x = x_0 + bk\), \(y= y_0-ak\)로 solution set을 parametrize하자.

\(x, y \ge 0\)이어야 하니, \(k \ge 0\)인 경우만 보면 된다는 것을 알 수 있다. 

이제 목표는 \(k \ge 0\), \(x_0+bk \ge 0\), \(y_0-ak \ge 0\), \(\text{gcd}(x_0+bk, y_0-ak)=1\)인 정수 \(k\)가 존재하는지 여부다. 

꽤 어려운 문제처럼 보이지만, 알고리즘 문제를 푸는 입장에서 solution은 간단하다. 

단순히 \(k\)에 대해서 iterate 하면서, 조건을 만족하는 \(k\)가 나오면 YES를 찍고, 아니면 NO를 찍으면 된다. 

\(k \ge 0\), \(x_0+bk \ge 0\), \(y_0-ak \ge 0\)를 만족하는 정수 \(k\)의 개수는 \(10^{18}\)-scale까지 커질 수 있다는 것을 생각하자.

이 알고리즘이 시간 안에 답을 낸다는 사실은 (구현하면 0ms 뜬다) 수학적으로 전혀 자명하지 않다.

1년 반 전에 이 문제를 풀었을 때 이 점은 개인적으로 숙제로 남아 있었다.

오늘 이 풀이가 시간 안에 도는 이유를 아는 분에게 질문 받아서, 고민을 하는 시간을 가져 해답을 찾았다.

사실 이 블로그를 쓰는 이유도 풀이를 쓰는 것보단 이 해답을 기록하기 위한 것이다. 

Claim: 문제 조건에서 \(\text{gcd}(x_0+bk, y_0-ak)=1\)을 만족하는 최소의 음이 아닌 정수 \(k\)는 최대 \(2^{15}\)이다. 

이 Claim이 증명되면, 풀이가 시간 안에 도는 이유는 자명하다. 

\(k\)에 대한 iteration이 최대 \(2^{15}\)번 돌기 때문에, 코드의 시간복잡도는 대강 \(\mathcal{O}(2^{15} \log s)\) 정도가 된다.

이 정도의 시간복잡도/상수면, 코드가 0ms 안에 도는 것도 충분히 설명된다. 

Claim 증명

자연수 \(D\)가 있어, 각 \(k=0, 1, \cdots D-1\)에 대해 \(\text{gcd}(x_0+bk, y_0-ak) \neq 1\)이라 하자.

최대공약수가 \(1\)이 아니라는 것은 공통 소인수가 있다는 것이다. 

그러니 각 \(k=0, 1, \cdots , D-1\)에 대해 \(x_0+bk\)와 \(y_0-ak\)의 공통 소인수를 아무거나 하나 잡아서 이를 \(p_k\)라 하자.  

우선 \(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.