백준 온라인 저지 - 18163. Binary Matrix

https://www.acmicpc.net/problem/18163

18163번: Binary Matrix

$\mathbb Z_2$ 원소로 구성된 $N \times N$ 정사각행렬 $A$가 주어진다. ($N \leq 128$) 이때, 자연수의 부분 집합

$$ \{ n \in \mathbb N : \exists m \in \mathbb N,\: 1 \leq m < n \text{ and } A^m = A^n \} $$

의 최소값을 찾는 문제이다.

 

1. 행렬의 최소 다항식(minimal polynomial)

최소 다항식(minimal polynomial)은 체(field)에서 특정 원소에 대해 0의 값을 만들어내는 가장 낮은 차수의 일계수(monic) 다항식을 의미한다. 쉽게 말해서, 어떤 원소 $x$에 대해

$$ p(x) = x^n + c_{n-1} x^{n-1} + c_{n-2} x^{n-2} + \cdots + c_1 x + c_0 = 0 $$

을 성립하게 하는 가장 낮은 차수 다항식 $p$는 $x$의 최소 다항식이다.

 

가장 낮은 차수의 일계수 다항식이라는 정의에 의해 최소 다항식은 유일하다.

또한 만약 어떤 다항식 $q$가 $q(x) = 0$을 만족한다면, $q$는 $p$를 인수로 가진다. 왜냐하면 $q$를 $p$로 나눈 나머지를 $r$이라고 하고 $r \not\equiv 0$이라면, $\deg(r) < \deg(p)$ 이면서 $r(x) = 0$ 이므로 정의에 모순되기 때문이다.

 

다시 본 문제로 돌아오자. 입력으로 주어진 행렬 $A$의 최소 다항식 $f$를 구한다. 만약 임의의 다항식 $g$가 $g(A) = 0$이 성립한다면, $g$는 $f$를 인수로 가진다. 우리는 즉 아래와 같은 순서로 문제를 해결할 수 있다.

1. 입력 행렬의 최소 다항식 $f$를 찾은 후
2. $f$를 인수로 가지는 최소 차수 다항식 $g(x) = x^n - x^m$를 찾으면 된다.

다행히도 1번 항목은 그리 어렵지 않다. 케일리-해밀턴 정리에 의해 $A$의 최소 다항식의 차수가 $N$ 이하임이 보장되어있기 때문이다.

최소 다항식을 계산하는 여러 방법이 있겠지만.. 나는 $A^0, A^1, A^2, \dots, A^N$ 행렬을 일차원 벡터로 펴서 가우스-조나단 소거법으로 계수를 구했다. 원소가 $\mathbb Z_2$이므로 비트 연산자와 궁합이 좋다. 나이브하게 짰는데도 아주 빠르게 계산되었다.

 

2. $x^k - 1$ 꼴의 다항식

상수항이 0이 아닌 다항식 $h$에 대해, $h(x)$를 인수로 가지는 최소 차수 다항식 $x^k - 1$을 생각해보자. 이러한 $k$를 $\alpha (h)$로 표기한다.

행렬 $A$의 최소 다항식을 간단히 인수분해하여 $f(x) = x^m f_0 (x)$로 나타낸다. ($f_0(0) \neq 0$) 우리가 구해야하는 답은 $\alpha(f_0) + \max(1, m)$이 된다.

 

$\mathbb Z_2[x]$에서 이진법으로 $1000...01$ 꼴로 표현되는 $x^k - 1$ (혹은 $x^k + 1$) 다항식은 아주 독특한 성질을 가지고 있다.

 

보조정리 2.1 $\gcd(x^a - 1, x^b - 1) = x^{\gcd(a, b)} - 1$ 이다.

$a > b$라고 가정하자. $x^a - 1 = (x^b - 1) x^{a - b} + x^{a - b} - 1$ 이므로 $\gcd(x^a - 1, x^b - 1) = \gcd(x^{a-b} - 1, x^b - 1) = \cdots = \gcd(x^b - 1, x^{a \:\operatorname{mod}\: b} - 1)$ 이다. 유클리드 호제법과 같은 논리가 성립한다.

 

따름정리 2.2 $x^a - 1$이 $x^b - 1$을 인수로 가질 필요충분조건은 $a$가 $b$로 나누어떨어지는 것이다.

 

보조정리 2.3 다항식 $f$에 대해 $f(x) | x^k - 1$ 이면 $\alpha(f) | k$ 이다.

$f(x) | x^{\alpha(f)} - 1$ 이므로 $f(x) | \gcd(x^{\alpha(f)} - 1, x^k - 1)$ 이다. $\gcd(x^{\alpha(f)} - 1, x^k - 1) = x^{\gcd(\alpha(f), k)} - 1$ 인데, $\gcd(\alpha(f), k) < \alpha(f)$ 라면 $\alpha(f)$가 최소라는데 모순이므로, $\alpha(f) | k$ 이다.

 

보조정리 2.4 두 다항식 $f$, $g$에 대해 $f | g$ 이면 $\alpha(f) | \alpha(g)$ 이다.

$f | g$ 이고 $g(x) | x^{\alpha(g)} - 1$ 이고, 보조정리 2.3에 의해 $\alpha(f) | \alpha(g)$ 이다.

 

정리 2.5 서로소인 두 다항식 $f, g$에 대해 $\alpha(fg) = \operatorname{lcm}(\alpha(f), \alpha(g))$ 이다.

우선 $\alpha(f) | \alpha(fg)$, $\alpha(g) | \alpha(fg)$ 이므로 $\operatorname{lcm}(\alpha(f), \alpha(g)) | \alpha(fg)$ 이다.

$l \triangleq \operatorname{lcm}(\alpha(f), \alpha(g))$라고 하자. $x^{\alpha(f)} - 1 | x^l - 1$, $x^{\alpha(g) - 1} | x^l - 1$ 이므로 $\operatorname{lcm}(x^{\alpha(f)} - 1, x^{\alpha(g)} - 1) | x^l - 1$ 이다. 보조정리 2.3에 의해 $\alpha\left(\operatorname{lcm}(x^{\alpha(f)} - 1,x^{\alpha(g)} - 1)\right) | \operatorname{lcm}(\alpha(f), \alpha(g))$ 이고, $fg | \operatorname{lcm}(x^{\alpha(f)} - 1, x^{\alpha(g)} - 1)$ 이므로 $\alpha(fg) | \operatorname{lcm}(\alpha(f), \alpha(g))$ 이다.

그러므로 $\alpha(fg) = \operatorname{lcm}(\alpha(f), \alpha(g))$ 이다.

 

정리 2.5는 아주 중요한 점을 시사해준다. 다항식을 서로소가 되도록 분해한 후, 각자 $\alpha$값을 계산하여 최소공배수를 구하면 되기 때문이다.

본 문제에 대한 풀이 방향은 아래와 같이 세분화 될 수 있다.

1. $f_0$를 인수분해한다. (Recall. $f(x) = x^m f_0(x)$)
2. 각 다항식 인수에 대해 $\alpha$ 값을 구한다.
3. 이들의 최소공배수 값을 구한다.

 

3. 기약 다항식(irreducible polynomial)

다항식의 인수분해와 $\alpha$ 함수의 계산에 앞서 기약 다항식(irreducible polynomial)의 중요한 성질을 짚고 간다.

기약 다항식이란 더 낮은 차수의 다항식의 곱으로 표현되지 않는 식을 의미한다. 정수론에서 소수(prime number)와 상당히 닮아있다.

정수론에서 소수 $p$에 대한 모듈러 곱 군(group) $\mathbb Z^*_p$를 정의했듯이 다항식에서도 비슷하게 정의할 수 있다.

 

$\mathbb Z_2[x]$에서 $n$차 기약 다항식 $f$를 고려해보자. $\mathbb Z_2[x]$의 부분집합

$$ \mathbb Z_2 [x] / f ^* \triangleq \{ g \:\operatorname{mod}\: f \::\: g \in \mathbb Z_2[x] \} \setminus \{ 0 \} $$

는 곱 연산에 대한 역원이 존재하여 곱셈 군(group)을 형성한다. 임의의 $g \in \mathbb Z_2[x] / f^*$에 대해 항상 역원이 존재하는 이유는, 확장 유클리드 호제법을 사용하여 $f(x) a(x) + g(x) b(x) \equiv 1$을 만족하는 $a, b$를 찾을 수 있고, 여기서 $b$가 $g$의 곱셈에 대한 역원이기 때문이다.

 

$| \mathbb Z_2 [x] / f ^* | = 2^n - 1$ 이므로, 라그랑주 정리에 의해 임의의 순환 부분군(cyclic subgroup)의 위수(order)는 $2^n - 1$의 약수이다.

따라서 임의의 $g \in \mathbb Z_2[x] / f ^*$에 대해 $g^{2^n - 1} \equiv 1 \:\operatorname{mod}\: f$이다.

즉 임의의 $n$차 기약 다항식 $f$에 대해 $x^{2^n - 1} \equiv 1 \:\operatorname{mod}\: f$ 이므로, $\alpha(f) | (2^n - 1)$이 성립한다. 그러므로, 아래 알고리즘으로 기약 다항식에 대한 $\alpha$ 값을 찾을 수 있다.

 

알고리즘 3.1 [입력: $n$차 기약 다항식 $f$ / 출력: $\alpha(f)$ 값] $2^n - 1$의 약수들 $p$를 나열해보면서, $x^p \equiv 1 \:\operatorname{mod}\: f$를 만족하는 $p$의 최소값을 찾는다.

 

정리 2.5 덕분에 알고리즘 3.1의 활용 가능성이 조금 더 넓어진다.

입력으로 주어지는 다항식 $f$가 꼭 기약 다항식일 필요가 없다. $f = f_1 f_2 \cdots f_k$ 이고, $f_1, f_2, \dots, f_k$가 모두 차수가 $n$인 서로 다른 기약 다항식이라면, 똑같이 $\alpha(f) | (2^n - 1)$이 성립한다. 왜냐하면 결국 $\alpha(f) = \operatorname{lcm}\{\alpha(f_1), \alpha(f_2), \dots, \alpha(f_k)\}$이기 때문이다.

 

알고리즘 3.2 [입력: 하나 이상의 서로 다른 $n$차 기약 다항식의 곱 $f$ / 출력: $\alpha(f)$ 값] $2^n - 1$의 약수들 $p$를 나열해보면서, $x^p \equiv 1 \:\operatorname{mod}\: f$를 만족하는 $p$의 최소값을 찾는다.

 

$2^n - 1$이 홀수이므로 알고리즘 3.2의 반환 결과 또한 홀수이다. (5절에서 사용되는 논의이다.)

중요한 성질이 하나 더 있다.

 

정리 3.3 자연수 $n$에 대해, 차수가 $n$의 약수인 모든 $\mathbb Z_2[x]$ 기약 다항식의 곱은 $x^{2^n} - x$ 이다.

$f \triangleq x^{2^n} - x$로 두자. $\gcd(f, f') = \gcd(f, 1) = 1$ 이므로 $f$는 square-free 임을 안다. (4-1 SFF 알고리즘 참조)

또한 두 자연수 $n, m$에 대해 $2^n - 1 \:\operatorname{mod}\: (2^m - 1) = 2^{n \:\operatorname{mod}\: m} - 1$ 이다. 유클리드 호제법에 의해 $\gcd(2^n - 1, 2^m - 1) = 2^{\gcd(n, m)} - 1$ 임을 알 수 있다.

이제 $n$에 대한 강한 수학적 귀납법으로 증명한다. $n$보다 차수가 작거나 같은 기약 다항식 $g$를 고려한다. $d \triangleq \deg(g)$라고 하자. $d | n$ 이면 $2^d - 1 | 2^n - 1$ 이고, 보조정리 2.1에 의해 $g | x^{2^d - 1} - 1 | x^{2^n - 1} - 1$ 이다.

$d \not| n$ 이라고 가정하자. $2^d - 1 \not| 2^n - 1$ 이다. 만약 $g | x^{2^n - 1} - 1$ 이라면, $g | \gcd(x^{2^d - 1} - 1, x^{2^n - 1} - 1) = x^{2^{\gcd(n, d)} - 1} - 1$ 이다. 여기서 $k \triangleq \gcd(n, d) < d$ 인데, 귀납법 가정에 의해 $x^{2^k} - x$은 차수가 $k$의 약수인 모든 기약 다항식의 곱이므로, 차수가 $d(>k)$인 $g$로 나누어 떨어지지 않는다. (모순) 따라서 $g \not| x^{2^n - 1} - 1$ 이다.

이와 같이 $x^{2^n} - x$는 차수가 $n$의 약수인 기약 다항식 나누어떨어지고, 차수가 $n$의 약수가 아닌 기약 다항식으로 나누어 떨어지지 않는다. 동시에 square-free로 중복 인수를 가지지 않는다. 따라서 차수가 $n$의 약수인 모든 기약 다항식의 곱은 $x^{2^n} - x$ 이다.

 

4. 다항식의 인수분해

다항식 인수 분해는 영문 위키피디아 "Factorization of polynomials over finite fields" 문서를 참고했다.

크게 아래 세 단계를 거쳐서 인수분해한다. 여기서 square-free라는 것은, $1$을 제외한 제곱수를 인수로 가지지 않는 상태를 의미한다.

1. (SFF; Square-Free Factorization) 임의의 $n$차 다항식 $f$를 입력으로 받아서, $f = g_1^1 g_2^2 g_3^3 \cdots g_n^n$를 만족하는 서로소인 square-free 다항식들 $(g_1, g_2, \dots, g_n)$을 반환한다.
2. (DDF; Distinct-Degree Factorization) Square-free 다항식 $g$를 입력으로 받아서, $g = h_1 h_2 h_3 \cdots h_m$인 $(h_1, h_2, \dots, h_m)$을 반환한다. 여기서 각 $k = 1, 2, \dots, m$에 대해 $h_k$는 [$1$ 이거나] 또는 [서로 다른 한 개 이상의 $k$차 기약 다항식들의 곱]이다.
3. (EDF; Equal-Degree Factorization) 서로 다른 한 개 이상의 $k$차 다항식들 곱 $h_k$를 입력으로 받아서, 기약 다항식의 곱으로 완전히 인수분해한 결과 $h_k = t_{k,1} t_{k,2} \cdots t_{k, l}$을 반환한다.

예를 들어, $f(x) = x^3 (x+1)^3 (x^2 + x + 1)^2 (x^3 + x + 1)^3$ 이라면, SFF를 거친 결과는 $g_1(x) = 1, g_2(x) = x^2 + x + 1, g_3(x) = x (x+1) (x^3 + x + 1)$ 이다. DFF에 $g_3$를 입력으로 준다면, $h_1(x)  = x (x+1), h_2(x) = 1, h_3(x) = x^3 + x + 1$ 이 반환된다. 마지막으로 EDF에 $h_1$을 입력으로 준다면 $t_{k,1} = x, t_{k,2} = x+1$으로 완전히 인수분해가 된다.

 

사실 본 문제를 푸는데는 2단계까지만 수행해도 충분하다. 1단계와 2단계의 세부 과정을 아래에 기술하겠다.

 

4-1. SFF (Square-Free Factorization)

입력으로 들어온 $n$차 다항식 $f$가

$$ f = \prod_{i=1}^n g_i ^ i = g_1^1 g_2^2 g_3^3 \cdots g_n^n $$

로 표현된다고 가정하자. (각 $g_i$ 들은 서로소인 square-free 다항식이다.) $f$의 미분 $f'$을 고려하자. 곱의 미분 공식에서 홀수 항만 살아남아 아래와 같이 나타난다.

$$ f' = \left( (g_1)' g_2^2 g_3^3 \cdots g_n^n \right) + \left( g_1^1 g_2^2 (g_3)' g_3^2 g_4^4 \cdots g_n^n \right) + \left( g_1^1 g_2^2 g_3^3 g_4^4 (g_5)' g_5^4 \cdots g_n^n \right) + \cdots$$

$g_i$가 서로 다른 기약 다항식의 곱이므로, $\gcd(g_i, g_i') = 1$ 이다. 그러므로

$$ \gcd(f, f') = (g_2 g_3)^2 (g_4 g_5)^4 (g_6 g_7)^6 \cdots $$

로 제곱수가 된다. 이의 제곱근(how?)은 아래와 같다.

$$ \sqrt{\gcd(f, f')} = (g_2 g_3) (g_4 g_5)^2 (g_6 g_7)^3 \cdots $$

 

$\sqrt{\gcd(f, f')}$ 에 대해 SFF 알고리즘을 재귀적으로 사용하여 $(g_2 g_3), (g_4 g_5), (g_6 g_7), \dots$ 다항식 결과를 얻었다고 가정하자.

그렇다면 $g_1, g_2, g_3, \dots, g_n$을 아래 방식으로 계산할 수 있다.

$$ \begin{align*} g_{2i + 1} &= \gcd \left( f / \gcd(f, f'),\: g_{2i} g_{2i + 1} \right) \\ g_{2i} &= (g_{2i} g_{2i+1}) / g_{2i + 1} \\ g_1 &= \frac{f / \gcd(f, f')}{g_3 g_5 g_7 \cdots} \end{align*} $$

왜냐하면 $f / \gcd(f, f') = g_1 g_3 g_5 \cdots$ 이기 때문이다.

 

4-2. DDF (Distinct-Degree Factorization)

입력으로 들어온 $n$차 square-free 다항식 $g$가

$$ g = \prod_{i=1}^n h_i = h_1 h_2 h_3 \cdots h_n $$

으로 가공된다고 가정한다. (단, $h_i$는 [$1$이거나] 또는 [서로 다른 한 개 이상의 $i$차 기약 다항식의 곱])

 

그렇다면 $h_k$는, 모든 $i = 1, 2, \dots, k - 1$에 대해 $x^{2^i} - x$과 서로소이다.

그렇지 않다면 정리 3.3에 의해 $h_k$는 차수가 $k$ 미만인 기약 다항식을 인수로 가지게 되기 때문이다.

굳이 $x^{2^i} - x$ 이라는 커다란 다항식을 쓰지 않아도 된다. $(x^{2^i} - x) \:\operatorname{mod}\: g$ 로도 충분하다.

즉, 아래 알고리즘으로 DDF 과정을 수행할 수 있다.

 

알고리즘 4.2.1 (DDF 구현) 아래 과정을 $i = 1$부터 $n$까지 반복하고, $(h_1, h_2, \dots, h_n)$을 반환한다.

1. $h_i = \gcd(g, (x^{2^i} - x) \:\operatorname{mod}\: g)$를 계산한다.
2. $g = g / h_i$로 갱신한다.

 

5. 인수분해 결과 취합하기

DDF의 결과로 $g = h_1 h_2 \cdots h_n$을 얻고, 각 $h_i$에 대해 알고리즘 3.2를 사용하여 $\alpha(h_i)$를 계산했다고 가정하자.

이 결과는 조심히 합쳐야한다. 우선 SFF에서 $g$의 지수가 $k$였다면, $\alpha(g)$로부터 $\alpha(g^k)$를 계산하는 과정이 필요하다.

 

우선 자연수 $x$에 대해, $LSB(x) = \max \{2^t : 2^t | x\}$로 정의한다. 예를 들어, $LSB(3) = 1, LSB(6) = 2, LSB(12) = 4, LSB(8) = 8$ 이다.

 

보조정리 5.1 임의의 자연수 $a, k$에 대해, $(x^a - 1)^{2^k} = x^{2^k a} - 1$ 이다. (수학적 귀납법)

 

보조정리 5.2 임의의 자연수 $a, k$에 대해, $\max\{t : (x^a - 1)^t | (x^{ka} - 1)\} = LSB(k)$ 이다. 또한, $\gcd\left(x^a - 1, \frac{x^{ka} - 1}{(x^a - 1)^{LSB(k)}} \right) = 1$ 이다.

우선 $(x^a - 1)^{LSB(k)} = x^{LSB(k)a} - 1$ 이고, $LSB(k)a | ka$ 이므로 $(x^a - 1)^{LSB(k)} | x^{ka} - 1$ 이다.

$o = k / LSB(k)$, $X = x^{LSB(k)a}$로 나타내자. $o$는 홀수이고, $\frac{x^{ka} - 1}{(x^a - 1)^{LSB(k)}} = X^{o-1} + X^{o-2} + \cdots + X + 1$ 이다. $X - 1$는 이진법으로 나타냈을 때 두 $1$이 $LSB(k)a$만큼, $x^a - 1$은 $a$만큼 떨어진 다항식이다. 이를 이용하면 $X^{o-1} + X^{o-2} + \cdots + X + 1$를 $x^a - 1$로 나눈 나머지는 $1$임을 알 수 있다. 유클리드 호제법에 따라 최대공약수도 $1$이다.

 

보조정리 5.3 하나 이상의 서로 다른, 같은 차수의 기약 다항식 곱 $g$에 대해, $\alpha(g^k) = \alpha\left( (x^{\alpha(g)} - 1)^k \right)$ 이다.

우선 알고리즘 3.2의 반환 결과인 $\alpha(g)$는 $2^n - 1$의 약수이므로 홀수다. $p(x) = x^{\alpha(g) + 1} - x$로 두면 $\gcd(p, p') = \gcd(p, 1) = 1$이므로 $p$는 square-free 이다. 따라서 $x^{\alpha(g)} - 1$ 또한 square-free이고, $g$로 나누어떨어지지만 $g^2$으로 나누어떨어지지는 않는다.

보조정리 2.4에 의해 $\alpha(g) | \alpha(g^k)$ 이라는 점도 살피고 가자.

 

$g^k | (x^{\alpha(g)} - 1)^k$ 이므로 보조정리 2.4에 의해 $\alpha(g^k) | \alpha \left( (x^{\alpha(g)} - 1)^k \right)$ 이다.

$u = \max \{t : (x^{\alpha(g)} - 1)^t | (x^{\alpha(g^k)} - 1) \}$으로 정의한다. 보조정리 5.2에 의해 $\gcd(x^{\alpha(g)} - 1, \frac{(x^{\alpha(g^k) - 1})}{(x^{\alpha(g)} - 1)^u}) = 1$이다. 만약 $u < k$이라면, $g | \frac{(x^{\alpha(g^k) - 1})}{(x^{\alpha(g)} - 1)^u}$ 이어야하는데, $g | (x^{\alpha(g)} - 1)$ 이므로 모순이다. 따라서 $u \geq k$이고, $\alpha \left( (x^{\alpha(g)} - 1)^k \right) | \alpha(g^k)$ 이다.

 

정리 5.4 $k$보다 크거나 같은 2의 제곱수 중 가장 작은 값을 $\beta(k)$라고 하자. (예를 들어, $\beta(1) = 1, \beta(2) = 2, \beta(3) = 4, \beta(5) = 8$이다.) 하나 이상의 서로 다른, 같은 차수의 기약 다항식 곱 $g$에 대해, $\alpha(g^k) = \beta(k) \alpha(g)$ 이다.

보조정리 5.3에 의해 $\alpha(g^k) = \alpha\left( (x^{\alpha(g)} - 1)^k \right)$이다. 이는 $\alpha(g)$의 배수이므로 $t \cdot \alpha(g)$로 나타낼 수 있다.

보조정리 5.2에 의해 $LSB(t) \geq k$ 이므로 $t \geq \beta(k)$ 이다. $\alpha$의 최소성에 의해 $t = \beta(k)$ 이다.

따라서 $\alpha(g^k) = \beta(k) \alpha(g)$ 이다.

 

정리 5.4는 $\alpha(g)$로부터 $\alpha(g^k)$를 구하는 과정을 설명한다. 이로부터 DDF 결과를 SFF 결과로 수합할 수 있고, 최종 답을 구할 수 있다.

 

6. 정리

위 배경지식을 종합하면 본 문제를 풀어낼 수 있다. 정확히는, 아래 순서를 통해 풀어낸다.

1. 입력 행렬 $A$의 최소 다항식 $f$를 계산한다. 이를 $f(x) = x^m f_0(x)$ 꼴로 기본적인 인수분해를 한다. ($f_0(0) \neq 0$)
2. SFF 알고리즘으로 $f_0 = \prod_i g_i^i$로 분해한다.
3. $g_i \neq 1$인 모든 $g_i$에 대해 DDF 알고리즘을 사용하여 $g_i = \prod_j h_{i,j}$ 형태로 분해한다.
4. $h_{i,j} \neq 1$인 모든 $h_{i,j}$에 대해 알고리즘 3.2로 $\alpha(h_{i,j})$를 구한다. 이로부터 $\alpha(g_i)$를 구한다.
5. $\alpha(g_1^1), \alpha(g_2^2), \alpha(g_3^3), \dots, \alpha(g_n^n)$을 계산하고, 이로부터 $\alpha(f_0)$를 구한다.

몇 가지 팁을 더 적자면..

• $2^n - 1$의 소인수를 미리 계산해서 상수로 넣었다. 시간 소요가 많은 작업이기 때문이다. 큰 소인수가 몇몇 있던 탓에 생각보다 골치가 아팠다..
• 답이 128비트 정수로 표현가능한지는 잘 모르겠다.. 나는 혹시라도 몰라서 BigInt 구현도 같이했다. (OS 과제가 생각났다..) 물론 다른 분들의 코드를 보니, 범위를 초과하는 답 몇 개만 미리 계산해놓고 문자열 형태로 출력하는 것 같았다.
• 풀이 설계 만큼이나 구현 난이도도 높다. 나는 마치 C++ 프로젝트처럼 여러 헤더/소스 파일을 만들어서 각각 유닛테스트를 마치고, 마지막에 하나의 파일로 수합하여 제출하는 방식으로 풀었다. End-to-end로 코딩하기에는 정말 어려운 문제임에 틀림없다..

 

---

 

정말 멋진 문제다. 외람된 말이지만, 출제하신 키파님의 뇌를 한 번 후벼보고 싶을 정도이다. 푸는 과정에서 많은 지식을 쌓을 수 있었다.

 

나는 "Proof by AC"라는 말을 그다지 좋아하지 않는다. 정리 2.5와 5.4는 풀이에 중추적인 역할을 하지만, 실제로 푸는 과정에서는 직관에 의존해서 세운 명제들이라.. 풀고나서도 그렇게 개운하지 않았다. 블로그에 포스팅하는 과정에서 이를 엄밀하게 증명할 수 있었고, 드디어 개운하게 생각을 마무리 지을 수 있을 것 같아서 기쁘다.