rkm0959

관련 코드는 github에서 찾아볼 수 있다.

이 주제도 이미 좋은 자료가 있습니다. https://casterian.net/archives/609

사실 3단원까지만 잘 이해해도 CP/PS 하는데는 문제가 없습니다. 레드까지는 문제 없을듯 ㅋㅋ 

소개가 늦었지만, 앞서 다룬 $ax \equiv b \pmod{c}$와 같이 mod 연산을 다루는 방정식을 합동식이라 한다.

중국인의 나머지 정리는 자연수 $a_1, n_1, a_2, n_2, \cdots , a_k , n_k$가 주어졌을 때, 연립합동식 $$ x \equiv a_i \pmod{n_i} \quad i = 1, 2, \cdots k $$를 푸는 알고리즘이다. 우리의 첫 목표는 $k=2$인 경우를 푸는 것이다. 나중에 가면 알겠지만, $k=2$만 풀면 끝이다.

$x \equiv a_1 \pmod{n_1}$, $x \equiv a_2 \pmod{n_2}$가 성립한다고 가정하자. 정의상, $x = n_1 y + a_1$인 정수 $y$가 있다.

그러니 우리는 $n_1y + a_1 \equiv a_2 \pmod{n_2}$, 또는 $n_1 y \equiv a_2 - a_1 \pmod{n_2}$를 풀면 된다.

그런데 이러한 형태의 합동식은 이미 푸는 방법을 알고 있다. 바로 앞에서 배웠기 때문.

• $g = \text{gcd}(n_1, n_2)$라 하자. 만약 $a_2-a_1$이 $g$의 배수가 아니라면 해는 존재하지 않는다.
• 만약 $a_1 \equiv a_2 \pmod{g}$라면, 앞선 결과에서 우리는 $y \equiv t \pmod{n_2/g}$ 형태의 결과를 얻는다.
• 이는 다른 말로, 적당한 자연수 $m$이 있어서 $y = (n_2/g) m  + t$이라는 것이다.
• $x = n_1y + a_1$에 그대로 대입하면, $x = (n_1n_2/g) m + (n_1t+ a_1)$이다. 즉, $x \equiv (n_1t+ a_1) \pmod{n_1n_2/g}$.
• 여기서 $n_1n_2 / g$가 $\text{lcm}(n_1, n_2)$임을 확인하자. $\text{gcd}(a, b) \times \text{lcm}(a, b) = a \times b$라는 결과 때문.

결국 $k=2$일 때의 결론은, 연립합동식이 해가 없거나 아니면 $x \equiv \text{something} \pmod{\text{lcm}(n_1, n_2)}$라는 결론을 얻는다는 것이다.

이는 연립합동식의 해가 존재하는 경우, 두 합동식을 하나의 합동식으로 합칠 수 있다는 의미가 된다.

• Example. $x \equiv 17 \pmod{42}$, $x \equiv 23 \pmod{60}$을 풀어보자.
• $x \equiv 17 \pmod{42}$에서, $x = 42m + 17$이라고 쓸 수 있다. 
• 이제 $42m + 17 \equiv 23 \pmod{60}$을 풀자. 이는 $42m \equiv 6 \pmod{60}$을 푸는 것과 같다.
• 앞에서 배운 방식을 생각하면, $42m+60n = 6$을 풀면 된다. $\text{gcd}(42, 60) = 6$이므로, $6$으로 식을 나누자.
• $7m+10n = 1$을 풀자. 이는 확장 유클리드 알고리즘으로 가능하며, $m=3$, $n=-2$를 얻는다.
• 여기서 우리는 $m \equiv 3 \pmod{10}$을 얻는다. $m=10t+3$이라 쓰고, $x=42m+17$에 대입하자.
• 그러면 $x = 42(10t+3)+17 = 420t + 143$을 얻고, 이는 $x \equiv 143 \pmod{420}$을 의미한다. 

이제 $k \ge 3$인 경우도 간단하게 해결할 수 있다. 두 합동식을 하나의 합동식으로 합치는 것을 반복하기만 하면 된다.

만약 중간 과정에서 "해가 없다"라는 결론이 나온다면, 전체 연립합동식 역시 해가 없다는 것을 바로 파악할 수 있다.

중국인의 나머지 정리, Chinese Remainder Theorem을 줄여서 CRT로 많이 부른다. 

중국인의 나머지 정리의 심화/응용 내용으로 Garner's Algorithm이 있다. CRT로 큰 수를 다루는 방법이다. 관심이 있다면 링크 참조.

관련 코드는 github에서 찾아볼 수 있다.

이 주제는 이미 좋은 자료가 있습니다. https://casterian.net/archives/601

이 글은 유클리드 알고리즘은 이미 어느 정도 숙지한 독자를 위해 작성하였다. 유클리드 알고리즘 관련 자료 역시 많다.

글의 핵심 목적은 유클리드 알고리즘의 핵심 아이디어 2개를 짚고, 확장 유클리드 알고리즘도 사실 별반 다를 거 없다는 것을 주장하는 것이다.

앞쪽 내용인만큼 제대로 이해해야 뒤 내용을 이해할 수 있으니, 시간을 많이 투자해보자. 

유클리드 알고리즘은 자연수 $a, b$가 주어졌을 때, $\text{gcd}(a, b)$를 구하는 방법이다. 결국 핵심 아이디어는

• 아이디어 1. 몫, 나머지를 구하여 $a = bq + r$로 쓰자. 이때 $\text{gcd}(a, b) = \text{gcd}(b, r)$이다. 
• Why? $g|a$, $g|b$가 성립한다고 가정하면 $g|(a-bq)=r$이므로, $g|b$, $g|r$.
• 반대로 $g|b$, $g|r$이 성립한다고 가정하면 $g|(bq+r)=a$이므로, $g|a$, $g|b$. 
• 즉, $g$가 $a, b$의 공약수인 것과 $g$가 $b, r$의 공약수인 것은 완전히 동치이다. 그러니 최대공약수 역시 동일.

• 아이디어 2. 위 사실은 문제를 $(a, b)$에서 $(b, r)$로 "축소"하는 방법을 제시해준다. 즉, $\text{gcd}(a, b)$를 구하는 문제를 $\text{gcd}(b, r)$을 구하는 문제로 축소.
• 얼마나 줄어들까? $a \ge b$를 가정하자. 그러면 $q \ge 1$이며 $2r \le (q+1)r = rq + r \le bq + r = a$이므로 $2r \le a$.
• 그러므로, $br \le (1/2) ab$임을 얻는다. 즉, 문제를 정의하는 두 인자의 곱이 적어도 반 이상은 감소한다.

두 아이디어를 합치면, 로그 시간을 거쳐서 최대공약수를 얻는 방법이 완성된다.

$(a, b)$를 $(b, r)$로 변환하는 과정을 거치면, 로그 시간 이내에 $(g, 0)$ 형태의 순서쌍을 얻는 것이 보장되기 때문이다.

이 시점에서 $\text{gcd}(a, b) = g$를 얻고, 알고리즘을 종료시키면 된다. 여기서부터는 구현의 문제다.

• Example. $\text{gcd}(576, 204)$를 구한다고 가정하자. 다음 과정을 거친다.
• $576 = 204 \times 2 + 168$이므로, $(576, 204)$에서 $(204, 168)$로 문제를 축소
• $204 = 168 \times 1 + 36$이므로, $(204, 168)$에서 $(168, 36)$으로 문제를 축소
• $168 = 36 \times 4 + 24$이므로, $(168, 36)$에서 $(36, 24)$로 문제를 축소
• $36 = 24 \times 1 + 12$이므로, $(36, 24)$에서 $(24, 12)$로 문제를 축소
• $24 = 12 \times 2 + 0$이므로, $(24, 12)$에서 $(12, 0)$으로 문제를 축소. 답은 이제 $12$. 

아이디어 1, 2는 CP/PS의 많은 정수론 문제에서 사용되는 아이디어다. 이를 유클리드 알고리즘의 활용에서 다룬다.

확장 유클리드 알고리즘은 자연수 $a, n$이 주어졌고 $\text{gcd}(a, n) = 1$일 때, $ax \equiv 1 \pmod{n}$인 $x$를 찾는 알고리즘이다.

(엄밀하게 말하자면, 자연수 $a, b$에 대하여 $ax + by = \text{gcd}(a, b)$인 $x, y$를 찾는 알고리즘이다. 사실상 똑같은 말)

이 문제를 바라보는 가장 정석적인 방법은 변수를 하나 추가하는 것이다.

• $ax \equiv 1 \pmod{n}$이라는 것은, 정수 $y$가 있어 $ax + ny = 1$이라는 것과 동치이다.
• 그러니 사실 우리는 $ax + ny = 1$을 만족하는 정수 순서쌍 $(x, y)$를 찾으면 된다. 
• 여기서 우리가 $\text{gcd}(a, n) = 1$이라는 조건을 추가한 이유도 알 수 있다. 위 식의 좌변이 무조건 $\text{gcd}(a, n)$의 배수이기 때문.

목표는 이제 $\text{gcd}(a, b) = 1$을 가정하고 $ax + by = 1$을 푸는 것이다. 문제를 바라보는 새로운 시각을 얻었으니, 위 아이디어 1, 2를 적용해보자.

• 아이디어 1. 몫, 나머지를 구하여 $a = bq+r$로 쓰자. $a, b$에 대한 문제를 $b, r$에 대한 문제로 바꿀 수 있는가?
• 가능하다. $ax + by = 1$은 $(bq+r)x + by = 1$과 동치이며, 정리하면 $b(qx+y) + rx = 1$로 쓸 수 있다.
• 그러니, $bx'+ry'=1$인 정수 순서쌍 $(x', y')$을 구하면, $qx + y = x'$, $x = y'$을 풀어 $ax + by = 1$인 $(x, y)$를 얻는다.
• 위 식을 다시 정리하면, 결국 $x = y'$, $y = x' - qy'$이므로, 이 순서쌍 $(x, y)$는 정수 순서쌍이다. 
• 이는 $(b, r)$에 대한 문제를 풀면, 빠르게 $(a, b)$에 대한 문제를 풀 수 있음을 의미한다.

• 아이디어 2. 역시 아이디어 1은 문제 축소의 의미를 담는다. 기존 유클리드 알고리즘에서 한 논의가 그대로 성립한다.
• 결과적으로, 위 과정을 로그번 거치면 결국 $(1, 0)$에 대한 문제를 해결하는 것으로 문제가 환원된다. 이는 $x=1, y=0$이라는 해가 있다.

두 아이디어를 합치면, 로그 시간을 거쳐서 조건을 만족하는 $x$를 찾을 수 있다. 이를 modular inverse라고 부르며, 이는 유일하게 존재한다.

알고리즘을 설명하는 과정에서 $ax + by = 1$을 만족하는 정수 순서쌍 $(x, y)$가 존재함까지 증명했음을 참고하자. 

나아가면, $ax + by = \text{gcd}(a, b)$인 $x, y$가 존재함을 얻는다. 이를 Bezout's Identity라고 한다.

• Example. $3x \equiv 1 \pmod{7}$을 만족하는 $x$를 구해보자.
• $3x + 7y = 1$인 정수 순서쌍 $(x, y)$를 찾으면 충분하다. 
• 이는 $3(x+2y) + y = 1$과 같다. 그러니 이제 $3a + b = 1$인 정수 순서쌍 $(a, b)$를 찾자.
• 이는 $1(3a+b) + 0a = 1$과 같다. 이제 $3a + b = 1$, $a = 0$을 풀어 $a = 0, b = 1$을 얻는다.
• 다시 위로 돌아가서, $3(x+2y) + y = 1$을 $3a + b = 1$로 변환한 것을 생각해보자.
• 우리의 목표는 이제 $x + 2y = 0$, $y=1$. 이를 풀면 $x= -2$와 $y = 1$을 얻는다.
• 실제로 $3(-2) \equiv 1 \pmod{7}$임을 쉽게 확인할 수 있다.

• $ax+by=1$이면, 각 정수 $t$에 대하여 $a(x+bt) + b(y-at) = 1$이 성립한다. 즉 $(x+bt, y-at)$ 역시 해.
• $t$를 잘 잡아서, $x+bt$가 $0$ 이상 $b$ 미만이 되도록 할 수 있다. overflow 방지를 위해 필요한 작업이다.
• 즉, 해를 재귀적으로 계산하는 과정에서, 해가 지나치게 크거나 작아지지 않도록 하는 과정이 필수적이다. 
• 위 Example을 보면 느낌이 오겠지만, 이 알고리즘은 재귀적으로 작성하는 것이 정신건강에 좋다.

더 나아가면, 아무런 가정 없이도 $ax \equiv b \pmod{n}$과 같은 식을 해결할 수 있다.

• 마찬가지 아이디어로, $ax + ny = b$라는 식을 해결하는 것으로 문제를 바꾸자.
• $g = \text{gcd}(a, n)$을 유클리드 알고리즘으로 구하자. 위 식의 좌변 $ax+ny$는 무조건 $g$의 배수임을 알 수 있다.
• 그러니, $b$가 $g$의 배수가 아니라면 해가 없음을 바로 알 수 있다. 
• 이제 $g|b$를 가정하고, 식을 $(a/g)x + (n/g)y = (b/g)$로 써보자. 이제 $\text{gcd}(a/g, n/g) = 1$이다.
• 확장 유클리드 알고리즘으로, $(a/g)x' + (n/g)y' = 1$인 정수 순서쌍 $(x', y')$을 찾을 수 있다.
• 이제 $x = (b/g)x'$, $y = (b/g) y'$을 선택하면 $ax + ny = b$임을 알 수 있다.
• 또한, $(x, y)$가 해라면 $(x + n/g \cdot t, y - a/g \cdot t)$ 역시 각 정수 $t$에 대하여 해임을 알 수 있다.
• 즉, $x \equiv \text{something} \pmod{n/g}$ 형태의 해를 얻는다. 자세한 디테일은 github 참고.

• Example. $12x \equiv 18 \pmod{54}$를 해결해보자.
• $12x + 54y = 18$을 해결하면 충분하다. $\text{gcd}(12, 54) = 6$임을 유클리드 알고리즘으로 계산한다.
• $18$은 $6$의 배수이니, 해가 존재한다. 식을 $6$으로 나누어주자. $2x + 9y = 3$을 얻을 수 있다.
• 이제 $\text{gcd}(2, 9) = 1$이니, $2x' + 9y' = 1$인 $x', y'$를 확장 유클리드 알고리즘으로 찾을 수 있다.
• $x'=5$, $y'=-1$을 찾았다고 하자. 이제 이 값을 $3$배 해주면 $x = 15$, $y = -3$을 얻는다.
• 이제 $x \equiv 15 \pmod{9}$, 또는 $x \equiv 6 \pmod{9}$가 답이 된다. 끝!  

사실 위 논의에서 일부 엄밀한 수학적 논의를 생략했다. 내용을 추가할 겸 간략하게 설명한다.

• 우리는 이미 확장 유클리드 알고리즘으로 $\text{gcd}(x, y) = 1$이면 $ax+by=1$인 정수 $a, b$가 존재함을 안다. (엄밀하게 증명한 것은 아니나, 나름 합리적으로 유도했다. "수학자들의 증명"을 원하면 당연히 정수론 책 참고.) 이를 통해 $\text{gcd}(a, b)=1$, $a|c$, $b|c$가 성립하면 $ab|c$가 성립함도 증명할 수 있다. 또한, $a|bc$이고 $\text{gcd}(a,b)=1$이면 $a|c$가 성립함도 증명할 수 있다. 특히, $g=\text{gcd}(a, b)$라면 $\text{gcd}(a/g, b/g)=1$이니 $a|bc$에서 $(a/g)|(b/g)c$를 얻고, 즉 $(a/g)|c$임 역시 얻을 수 있다. 즉, $a/\text{gcd}(a,b)$가 $c$의 약수가 되어야 한다. 이 "증명할 수 있다"라는 부분을 자세히 알고 싶다면 정수론 책 참고 or 댓글로 질문. 이 정도 내용은 알아야 정수론 문제 해결에 지장이 없을 것이라고 생각하여 추가한다.

• modular inverse는 유일한가? $x, y$가 모두 $\pmod{n}$에 대한 $a$의 modular inverse라고 하자. 그러면 가정 상 $\text{gcd}(a, n)=1$이고 $n|(ax-1)$, $n|(ay-1)$이니 두 식을 빼면 $n|a(x-y)$를 얻는다. 한편, $a|bc$이고 $\text{gcd}(a, b)=1$이면 $a|c$임이 알려져 있다. 그러므로 $n|(x-y)$를 얻고 $x \equiv y \pmod{n}$이 성립한다. 즉, modular inverse는 ($n$으로 나눈 나머지를 보았을 때) 유일함을 얻는다. 증명 끝.
• $ax \equiv b \pmod{n}$의 해는 정말 저게 다인가? $ax+ny=b$를 생각할 때, $(x, y)$가 해라면 $(x + n/g \cdot t, y - a/g \cdot t)$가 해임은 직접 대입을 통해서 자명하게 얻을 수 있다. 이것들만이 해라는 것 역시 보여야 한다. 만약 $ax+ny = ax'+ny'=b$라면, $a(x-x')=n(y'-y)$가 된다. 여기서 $x-x'$이 $n/g$의 배수, $y-y'$이 $a/g$의 배수임을 증명할 수 있다. 즉, 해가 되려면 $(x + n/g \cdot t, y - a/g \cdot t)$ 형태를 가져야 한다. 증명 끝.

관련 코드는 github에서 찾아볼 수 있다.

여기서는 잘 알려진 사실들부터 시작해서, 나중에 중요해질 수학적 사실들을 다룬다.

사실 1단원과 2단원 앞 유클리드 알고리즘만 알아도 퍼플/오렌지에 영향은 없다.

잘 알려진 사실들은, 매우 간단하게만 설명하고 스킵하자. 이미 좋은 자료/블로그가 많으니, 이를 참고하는 것 추천.

다음 사실은 유명하다 : 정수 $a, b$가 있고 $b \neq 0$일 때, $a = bq + r$이고 $0 \le r < |b|$인 정수 $q, r$이 유일하게 존재한다.

이때, $r$을 "$a$를 $b$로 나눈 나머지"라고 정의한다. 만약 $r = 0$인 경우, $a, b$는 서로 약수/배수 관계에 있다고 하며, $b|a$라 쓴다.

이를 통해서 공약수/공배수 개념을 정의할 수 있으며, 나아가 최대공약수/최소공배수의 개념을 정의할 수 있다.

자연수 $n \ge 2$가 각 $2 \le k < n$에 대하여 $k \nmid n$을 만족하면, $n$을 소수라고 부른다. 소수가 아니면 (1 제외) 합성수라고 부른다. 

이를 통해서 소인수분해라는 개념을 정의할 수 있으며, 이는 유일하다는 것이 잘 알려져 있다.

소인수분해를 통해서, 자연수의 약수의 개수와 약수들의 합 등을 계산할 수 있음은 교육과정에도 있는 내용이다.

만약 두 정수 $a, b$가 $n$으로 나눈 나머지가 같다면, $a \equiv b \pmod{n}$이라고 쓴다. 이는 $n|(a-b)$와 같은 뜻이다.

또한, $a$를 $n$으로 나눈 나머지를 $a \pmod{n}$이라고 쓰기도 한다. 다음은 간단 Exercise.

• 정수 $a, b, n$이 $a \equiv b \pmod{n}$이고, $r$이 정수인 경우, 다음이 모두 성립함을 보여라.
• $a + r \equiv b+ r \pmod{n}$, $a - r \equiv b - r \pmod{n}$, $ar \equiv br \pmod{n}$.

즉, mod 연산을 취하는 과정에서도 평소처럼 사칙연산을 할 수 있다. 

나눗셈이 문제인데, 다음 단원에서 modular inverse가 나오면 나눗셈도 modular inverse를 양변에 곱하는 방식으로 할 수 있다.

이 시점에서, 알고리즘 문제를 몇 개 생각해볼 수 있다. 모두 이미 자료가 많으므로, 빠르고 간단하게 한다.

• 자연수가 소수임을 어떻게 판별할 것인가?
• 자연수의 약수의 개수를 어떻게 셀 것인가? 약수를 모두 찾으라고 한다면 어떻게 할 것인가?
• 자연수의 소인수분해를 어떻게 구할 것인가?
• 1부터 $n$까지의 소수를 어떻게 셀 것인가/찾을 것인가?

첫 세 문제에 대해서는, $\mathcal{O}(\sqrt{n})$ 알고리즘이 잘 알려져 있다. 핵심 아이디어는,

• 자연수 $n$이 $2$ 이상 $\sqrt{n}$ 이하 모든 자연수에 의해 나누어떨어지지 않는다면, $n$은 소수다.
• 이유: 소수가 아니라면 $n = ab$이며 $1  < a , b < n$인 자연수 $a, b$ 존재. 둘 다 $\sqrt{n}$보다 크다면 $ab > n$.

이 핵심 아이디어로 세 문제를 해결해보자.

• 소수 판별: $2$ 이상 $\sqrt{n}$ 이하 모든 자연수에 대해 나누어떨어짐을 판별하면 끝.
• 약수 세기/찾기: $a$가 $n$의 약수면 $n/a$ 역시 $n$의 약수. 둘 중 하나는 $\sqrt{n}$ 이하고 하나는 $\sqrt{n}$ 이상이니, $\sqrt{n}$ 이하 약수만 찾으면 모든 약수를 알 수 있다.
• 소인수분해: $2$ 이상 $\sqrt{n}$ 이하 모든 자연수를 순서대로 보자. 현재 보고 있는 자연수 $i$가 $n$의 약수라면, $n$이 $i$의 배수가 아닐 때까지 $n$에서 $i$를 나누어준다. 나누어주는 횟수를 저장하는 것은 당연. 만약 iteration이 끝났을 때, $n$이 $1$이면 그대로 끝. 아니면 남은 $n$ 역시 소수이며, 기존 $n$의 소인수가 된다. 

마지막 문제는 "에라토스테네스의 체"로 잘 알려져 있는 결과다.

• 에라토스테네스의 체: 2부터 $n$까지 순서대로 보면서, 합성수인 것을 지워내자. 만약 지금 보는 값 $p$가 지워지지 않았다면, $p$는 소수다. 
• 이제 $p$의 배수를 ($p$는 빼고) 전부 지워내자. 이걸 반복하면 남는 것은 전부 소수. 예시를 인터넷에서 찾아보면서 이해해보자. 

에라토스테네스의 체는 활용 방법이 굉장히 많다. 다음을 할 수 있는 방법을 생각해보자. 해답은 github에 있다.

• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 가장 작은 소인수"를 계산하는 법
• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 서로 다른 소인수 개수"를 계산하는 법
• 오일러 파이 함수. $n$의 소인수분해가 $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$일 때, $\phi(n) = n \cdot \frac{p_1 - 1}{p_1} \cdots \frac{p_k-1}{p_k}$라 정의하자. 이 값을 모두 계산하는 법.
• 조금 더 난이도가 있지만, "약수의 개수"와 "약수의 배수" 역시 전처리 할 수 있다.

여기서 강력한 결과를 하나 얻을 수 있다.

• 각 $2$부터 $n$까지의 자연수에 대하여, "그 자연수가 갖는 가장 작은 소인수"를 미리 전처리했다고 가정하자.
• 이제 $2 \le m \le n$인 자연수 $m$의 소인수분해를 원한다고 가정하자. 
• $m$에서 시작해서, "가장 작은 소인수"를 나누어주는 과정을 반복하자. 한 번에 값이 반 이상 줄어드니, 로그 시간에 소인수분해 끝.

에라토스테네스의 체를 사용하면 $1, 2, \cdots , n$ 각각이 소수인지 전부 빠르게 판별할 수 있다.

하지만 꼭 $1$부터 시작할 필요는 없다. $A+1, A+2, \cdots , A+n$ 각각이 소수인지 빠르게 판별할 수는 없을까?

• $2$부터 $\sqrt{A+n}$까지의 수를 순서대로 보자. 현재 보고 있는 수를 $k$라고 하자.
• $A+1, A+2, \cdots , A+n$에 속한 $k$의 배수 중 $k$가 아닌 것을 전부 제거하자. 남는 것은 전부 소수이다.
• 시간복잡도는 어떻게 될까? 각 $k$에 대하여 제거되는 수의 개수는 $\mathcal{O}(n/k)$개이다.
• 이를 $k$를 $2$부터 $\sqrt{A+n}$까지 돌면서 더하면, 아래에서 다룰 Harmonic Sequence에 대한 성질에 의해 총 $\mathcal{O}(n \log n)$이 된다.
• 그러니 $k$에 대하여 for문을 돌리기 위해 필요한 시간 $\mathcal{O}(\sqrt{A+n})$을 더하면, $\mathcal{O}(\sqrt{A} + n \log n)$이라는 결과를 얻는다.
• 에라토스테네스의 체의 다양한 활용 방법을 이 방식에서도 그대로 적용할 수 있다.

참고할 점은, 위의 에라토스테네스의 체가 하는 일을 $\mathcal{O}(n)$에 하는 방법이 존재한다는 것이다.

• Linear Sieve라고 하는 테크닉이다. 이를 위해서는 ahgus89님의 이 자료나, 원본이라고 할 수 있는 이 글을 보자.
• 이후에 다룰 multiplicative function에 대한 글을 읽고 다시 위의 자료를 읽는 것이 이해하기 편할 수 있다.
• 이 가이드에서 굳이 Linear Sieve를 설명하지 않는 이유는, 필자도 Linear Sieve가 필요할 정도로 시간제한이 빡빡한 문제를 본 적이 없기 때문이다.
• 이 외에도, 에라토스테네스의 체는 다양한 최적화 방법이 있다. 개인적으로는 필요한 문제를 본 적이 없었다. 필요하면 나쁜 문제라는 것이 내 생각.
• 당연하지만, 이러한 체 최적화 방법을 알아둬서/팀노트에 넣어서 나쁠 것은 없다. 나중에 관심이 생기면 보는 것으로.

이제 여러 수학적 사실들을 빠르게 다룬다. 중요해지는 때가 온다.

• [매우 중요] 자연수 $n$에 대하여, $\lfloor n/1 \rfloor, \lfloor n/2 \rfloor, \cdots, \lfloor n/n \rfloor$ 중 서로 다른 것은 $\mathcal{O}(\sqrt{n})$개이며, 효율적인 iteration도 가능. github 참조.
• 이유가 꽤 아름다우니 설명한다. $\lfloor n/1 \rfloor, \cdots , \lfloor n / \lfloor \sqrt{n} \rfloor \rfloor$까지 서로 다른 것은 $\mathcal{O}(\sqrt{n})$개. (항 개수가 애초에 $\mathcal{O}(\sqrt{n})$개이므로)
• $\lfloor n / \lfloor \sqrt{n} \rfloor \rfloor, \cdots ,\lfloor n/n \rfloor$까지 서로 다른 것도 $\mathcal{O}(\sqrt{n})$개. (값들이 전부 $\mathcal{O}(\sqrt{n})$ 이하이므로)
• 위 github 코드의 iteration 방법의 원리가 궁금할 수 있을 것이다. 이것의 대한 설명은 ahgus89님의 이 글 참고.
• [매우 중요] Harmonic Sequence. 자연수 $n$에 대하여, $1/1 + 1/2 + 1/3 + \cdots + 1/n = \mathcal{O}(\log n)$.
• 7단원에서 언급하겠지만, 이를 통해서 $1$부터 $n$까지 약수의 개수 합이 $\mathcal{O}(n \log n)$임을 얻는다.
• 그러므로, 만약 필요하다면, $1$부터 $n$이 갖는 약수들을 std::vector 등 자료구조에 $\mathcal{O}(n \log n)$ 시간에 넣을 수 있다.
• 더욱 자세한 내용을 알고 싶다면, 7단원에서 "약수를 iterate 하는 것보다 배수를 iterate 하는 것이 쉽다"는 부분을 읽자.
• Merten's 2nd Theorem. 자연수 $n$에 대하여, $n$ 이하 소수들의 역수의 합은 $\mathcal{O}(\log \log n)$.
• Merten's 2nd Theorem으로, 에라토스테네스의 체의 시간복잡도를 파악할 수 있을 것이다. $\mathcal{O}( n \log \log n)$.
• 후반부의 내용에서, 은근슬쩍 자연수 $a, b, c$에 대하여 $\lfloor \lfloor a/b \rfloor / c \rfloor = \lfloor a/(bc) \rfloor$라는 식을 꽤 사용한다.

마지막으로, 모듈로 연산에 대해 잠깐 언급한다. 이 연산은 덧셈, 뺄셈에 비해서는 물론, 곱셈에 비해서도 느린 연산이다.

그러니, 모듈로 연산을 마구잡이로 사용하면 비효율적인 코드가 나오게 될 것이다. 이를 최적화하는 방법을 간단히 소개한다.

모듈로 연산 횟수를 줄이는 법

• 가능하면 진짜 나머지를 취하지 말고, 모듈러스를 더하고 빼는 것으로 대체한다.
• 예를 들어, $0 \le a < M$, $0 \le b < M$에 대해, $a+b \pmod{M}$을 계산하기 위해서 모듈로 연산을 쓰지 말자는 것이다.
• $a+b$를 계산한 다음, $M$보다 큰 경우 $M$을 빼는 것이 훨씬 효율적이다. 쉽고 확실한 최적화 방법이다.

모듈로 연산 자체를 빠르게 하는 방법

• 모듈로를 가능하면 const로 선언하자. 그러면 상당한 속도 개선을 확인할 수 있다.
• 이러한 고속화의 원리 중 하나는 Barrett Reduction이다. modulo 연산을 곱셈과 시프트 연산으로 대체한다.
• 자세한 내용을 알고 싶다면, 이 위키피디아 글과 이 min_25의 글을 확인하라.
• 어셈블리를 잘 아는 사람이라면 어셈블리를 이용할 수 있는 것으로 안다. 이 부분은 내가 모르니 생략. 이 링크를 보자.
• 관련 내용이 KAIST의 ICPC팀이었던 더불어민규당의 팀노트에도 있다. Fast LL Division/Modulo 부분을 보자.

PS를 위한 정수론 가이드를 쓰기로 했다. 이유는 여러 가지.

• 자료가 부족하다는 의견을 많이 듣고, 동의함
• kipa00님의 NTA가 매우 좋은 자료인 것은 맞지만, 진입장벽이 상당하다
• 수학적 직관이나 엄밀한 증명을 일부 포기하더라도 내용을 간결하게 전달하는 것이 필요한 것 같다
• (나중에 직관/증명이 필요하다면, 그 때 직접 자료를 찾으면 된다. 처음 들이박는 것보다 쉬울 것)
• 그래서 최대한 문제 풀이에 집중하는 가이드가 필요하다고 생각했다
• 그러나, 각 알고리즘의 기본 원리 정도는 배우고 갈 수 있도록 내용을 작성하였다.
• (목표는 PS 정수론을 입문하기 위해 책을 폈다가 수학적 귀납법부터 시작하면서 의지를 잃는 사람들을 배려하는 것) 

이론 설명은 여기에 간단하게 하고, 관련 코드를 github에 올릴 계획. git 연습도 해야하니. 

연습문제도 올릴 예정인데, 이건 천천히 할 생각이다. 초반 주제들은 solved.ac에 관련 태그가 많으니 활용하자.

글을 읽다보면 뭔가 논리에 빈 공간이 있다는 생각이 들 수도 있다. 정수론 책을 그대로 옮기고 싶지 않아서 그런 것이다.

논리의 허점에 아쉬움을 느끼는 때가 오면, 학부용 정수론 책을 사서 읽으면 도움이 될 것이다. 위에서도 말했지만..

(+ 당연한거지만 학부 정수론을 모르는 상태로 어려운 문제를 풀려고 하면 한계가 올 것이다. 그때 필요하면 책을 읽으면 된다. 앞 몇 장만 읽어도 도움된다.)

일단 내용을 최대한 빠르게 퀄리티 신경 안 쓰면서 뽑아내고, 지적이나 제안을 받아가면서 천천히 보완할 생각이다. 

한 번에 완벽한 자료를 만들려고 하면 한 3~4단원하고 접을 가능성이 99.9%라서인데 사실 이게 더 나을수도 ㅋㅋㅋㅋ

가끔 오개념을 글에 쓰고 난 다음 나중에 고치는 일이 생길 수 있어, 글이 올라온 뒤 조금 시간이 지난 다음 읽는 것을 추천한다.

추가적으로 해야하는 언급들

• 시간복잡도 분석은 빡빡하게 하지 않을 것이다. 본격적으로 시간복잡도를 논의하려면 정수 덧셈도 로그 시간이라는 내용들을 녹여내야한다. 하지만 PS/CP에서 이렇게 시간복잡도를 분석하는 경우는 흔치 않으니, 여기서도 모든 덧셈과 곱셈은 $\mathcal{O}(1)$ 연산이라는 것으로 합의하자. 
• 비슷하게, $\mathcal{O}$ notation도 꽤 편안하게 (엄밀하지 않게) 사용할 것이다. 적당히 이해하고 넘어가자 :)
• 자료 수정/추가는 가끔 오류가 보이거나 필요가 생기면 할 것이다. github에서도 수정이 많을 수 있다.
• github에 올라온 코드는 팀노트에 복붙해서 넣을 퀄리티가 아니라, proof of concept 정도로 보는 것이 나을 것이다.

solved.ac 기준. 1~3 및 5 초반은 플레 중하위권 이하, 4, 5 후반은 플레 중상위권, 6번은 플레, 7, 8은 플레 상위권, 9~11번은 다이아 이상.

예상 커리큘럼

1. 기본기 잡기
2. 유클리드, 확장 유클리드 알고리즘
3. 중국인의 나머지 정리
4. 페르마 소정리, 오일러 정리 및 활용
5. 팩토리얼과 이항계수
6. Miller-Rabin 소수 판별 알고리즘과 Pollard-Rho 소인수분해
7. Mobius function과 그 활용
8. 원시근, 이산로그, 이산제곱근
9. 유클리드 알고리즘의 활용
10. 소수의 개수 빠르게 세기
11. more on multiplicative functions
12. 개인적인 후기, 그리고 그 이후의 이야기

1단원은 이미 자료가 많은 부분을 다루어, 덜 친절할 예정이다. 이 부분은 다른 자료를 찾는 것을 추천한다.

UPD: 백준 문제집 - 6593번 ~ 6603번

질문은 댓글로 항상 환영 :) (나도 내가 설명을 쉽게 못하는 사람인 걸 안다)

I participated in PBCTF 2020 as a member of Super Guesser. We reached 2nd place :) 

Huge congratulations and respect to zer0pts, a team that clearly doesn't fit their team name.

I solved : QueenSarah2, Strong Cipher (with reversing help), LeaK, Special Gift, Special Gift Revenge, Find rbtree.

QueenSarah2

We have a secret permutation of bigrams, which are used to encrypt the messages. By sending all $27^2$ bigrams, we can easily calculate the square of the permutation. This is because with messages of length 2, we go through 2 rounds of encryption, and the last shuffle algorithm doesn't actually shuffle anything. However, knowing the square of the permutation does not imply we cannot recover the permutation directly. This is only possible in certain cases - such as when all cycles of the squared permutation have different length. This happens with around 2% probability. Therefore, we may try to recover the original permutation with this idea, and recover the flag by reversing the encryption process. I got it with around 20 tries, so I got lucky here a bit. Looking at the flag, it looks like there should be a cooler solution.

Strong Cipher

After reversing, we found out that the encryption process was a simple vigenere cipher, with $GF(2^8)$ multiplications instead of addition. By brute forcing key length and selecting keys that gave maximum number of readable characters, we can recover the plaintext. I wasted a lot of time by incorrectly assuming that the plaintext is 100% readable. oof

LeaK

It's yet another hidden number problem. We have

$$s \equiv k^{-1}(h + r \cdot pvk) \pmod{n}$$ $$ (2^{216} \cdot small_1 + 2^{40} \cdot leak + small_2)s \equiv h + r \cdot pvk \pmod{n}$$ $$ r \cdot pvk \equiv 2^{216}s \cdot small_1 + s \cdot small_2 + 2^{40}s \cdot leak - h \pmod{n}$$

Now we can work with $r$, $2^{216}s$, $s$ and $n$ to make $2^{40}s \cdot leak - h$. Babai's algorithm can do this.

Small notes on the code below - I have used the following tricks to get the secret key.

• The equation above is an equality, so we have to force it to be equal. 
• This is done by scaling - i.e. multiplying a super large integer $n^2$ to the respective columns.
• We have $pvk$ to be between $0$ and $n$, but $small_1, small_2$ between $0$ and $2^{40}$. 
• We need the two to have a similar order for CVP algorithm to respect the bounds on $small_1, small_2$, so scale it by $n/2^{40}$. 
• We have 30 signatures, but with the matrix below, using all of them takes too long. Using 10 is enough.

Special Gift

My best achievement in this CTF is first solving this with unintended sol, forcing rbtree to write a revenge challenge.

This problem is also the reason I'm writing stuff up for this CTF in 2am ^__^

My solution resembles my alternate solution for crypto01 from SECCONCTF a little bit.

We start with $$ ed = k\phi(n) + 1 = k(n-p-q+1)+1 = kn - k(p+q-1) + 1$$

Since $e \approx n$ and $d \approx n^{0.4}$, we have $k \approx n^{0.4}$ as well. Also, we know that $$ 2\sqrt{n} \le p+q \le 3\sqrt{n/2}$$ so combining, we have something like $0 \le k(p+q-1) - 1 \le 3 \cdot n^{0.9}$. I calculated constants like $3$ very loosely, btw. 

Therefore, we have an interval of length $3 \cdot n^{0.9}$ that $ed \pmod{n}$ must lie inside. 

Writing $d = gift \cdot 2^{120} + c$ with $0 \le c < 2^{120}$, we have an interval on $ec \pmod{n}$. 

We have $2^{120}$ candidates for $c$, and we have a condition on $ec \pmod{n}$ that has, heuristically, a probability of $3 \cdot n^{-0.1}$ of satisfying. Therefore, we can expect around $2^{120} \cdot 3 \cdot n^{-0.1} \approx 3 \cdot 2^{18}$ "true" candidates for $c$. This is not an unreasonably large number, so if we can find those true candidates quickly, we can brute force every one of them to find the flag. 

How do we find the true candidates for $c$? This is equivalent to finding the smallest positive integer $x$ such that $$L \le Ax \pmod{M} \le R$$ for given $A, M, L, R$ quickly. Polynomial time solution of this problem was mentioned in the crypto01 problem writeup linked above. 

It takes around 30 minutes to compute the flag, and it iterates over around 700,000 candidates as expected.

The flag prints the link to a paper that contains the intended solution.

Special Gift Revenge

Now this problem blocks the unintended sol above. Therefore, we should implement the paper in the previous flag.

The implementation is not tough, but I surely learned a lot of lattice stuff from it. Thanks to rbtree :)

The flag is pbctf{thank_you_rkm0959,_for_finding_unintended_solution} which is pretty cool :P

Find rbtree

I tried the most naive way - finding the question that has "the best worst case". If I had used all my queries and I still had multiple candidates left, I chose one randomly and reported it as the answer. It looked it had decent chances of succeeding, so my teammates ran multiple instances :) I was worried about the server being adaptive like some challenges in competitive programming, but we got the flag.

UPD: So more of a backstory - I had realized that the number of candidates never decreased by more than half. This is strange unless the server is set up against you. This was the main fact that caused me to become worried about adversarial server. Turns out the server *was* adversarial, but wasn't perfectly so. The solution below is clearly unintended (smarter solutions should exist) but the server's antics can't really stop it from getting the flag. I guess they didn't block choosing one random answer while there are multiple candidates. 

그래도 후기를 쓰기는 해야 할 것 같아서 ㅋㅋㅋㅋㅋ 아쉽지만 작년에 비해서 좋은 결과가 나오지는 못했다. 이유는

• 작년처럼 팀연습을 10번 이상 열심히 굴리지를 않았음 (올해 팀연습 0회)
• 팀들이 작년보다 전반적으로 강해지고 센 팀들도 더 등장함
• 일단 내가 작년에 비해서 간절함이 없었음 (애초에 작년에 뽑은 성과가 너무 좋았음) 

그래서 솔직히 결과에 아쉬움이 있어도 "이거 이상을 바라면 그건 그거대로 양심 X"라고 생각하고 있다.

아쉽다고 쳐도 9등이면 동상이고 이정도면 꽤 깔끔한 CP 대회 마무리 아닐까 싶기도 하고 ^__^ 

• 열었더니 B가 쉬워서 빠르게 풀었음
• A가 풀이 자체는 쉽다는 콜이 나옴. C 문제 해석에서 약간의 뇌절
• E가 풀만하다는 콜과 G도 쉽다는 콜이 나옴. G에서 함정 빠짐
• E 맞추고 G는 계속 맞왜틀. J 풀이 나옴. H가 simple FFT인거 보고 바로 구현, AC
• C도 풀이 나오고 L 준비 시작. J 짜서 AC. G 다른 풀이도 짜봤는데 또 틀림.
• G 함정 발견 및 C 구현 후 C, G 모두 AC. L은 DnC 콜이 나왔는데 틀리는 중.
• L DM 돌리면서 틀린 이유 발견. Money For Nothing 생각하면서 풀이 고쳐서 맞음
• 이제 junie가 A 구현하면서 다른 풀 거 찾아 떠남. I 보는게 맞는 판단인데 F가 할만해보여서 (ㅋㅋ) 시작
• F 문제 잘못 이해해서 SCC 문제인줄 알았음 ㅋㅋ
• junie가 A를 개고통받으면서 결국 AC 성공. 8솔해서 대충 이정도면 그래도 나쁘지 않다고 생각했음
• F 예제 만들어보다가 결국 문제 이해를 못해먹겠다는 결론을 얻고 그대로 사망

이제 내년부터 ICPC 판 재밌어질텐데 팝콘각이나 열심히 재야겟다 ^____^

2등상을 받았다. 실제 실력에 비해 너무 높은 상이다.

UPD: 상금과 트로피까지 전달 받았다. 이제 수상 소감이 올라오면 끝인데 얼굴 팔릴 생각에 걱정이다 ㅜㅜ

UPD: 수상 소감까지 올라왔습니다. 얼굴도 팔렸네요 ㅋㅋ;

대회 과정

• 1번 열었더니 쉬워서 빠르게 풀었다. 새로고침하니 퍼솔 같아서 기분이 좋았음 ^~^
• 2번 열고 일단 SCC를 짤 줄 알면 $\mathcal{O}(m^2)$이 뚝딱임을 파악했다
• 그런데 뇌절해서 그 풀이가 $\mathcal{O}(nm)$인 것으로 착각을 했다.
• 아무튼 $\mathcal{O}(m^2)$ 풀이를 짜서 긁으려고 했는데 틀리더라. 멘붕 옴
• 나중에 내 풀이가 $\mathcal{O}(nm)$이 아님을 깨달았다. 그래서 목표를 $\mathcal{O}(nm)$ 풀이 찾는 거로 잡았다.
• 그러다가 문제에 오류가 있다는 공지를 받고, $\mathcal{O}(nm)$ 풀이 찾기에 착수했다.
• 풀이 자체는 빠르게 나왔는데, 2번 문제치고 너무 복잡해서 뇌절이었나 걱정했다.
• 그런데 2번 데이터가 수정된 이후에도 만점자가 4명 뿐이더라. 시간이 꽤 지난 것 치고 적은 수였다.
• 그래서 맞는 풀이라는 확신을 할 수 있었고. 빠르게 짜서 바로 AC. 5번째 솔브로 기억한다. 이때가 1시간 정도 지났을 때.
• 3번을 열었는데 일단 문자열에다가 드럽게 복잡한 것 같아서 일단 걸렀다. 전날에 연습을 좀 했는데 힘겨워서 ㅋㅋ
• 그래도 3번은 풀어야 한다고 생각을 했고, 그 전에 4, 5번에서 빠르게 긁을 수 있는 것을 긁어오는 게 좋다고 판단했다.
• 4번을 열었는데, 일단 마음 속으로 $\mathcal{O}(n^3 \log n \log MAX)$ 쯤 되는 풀이가 나왔다. 4-2까지 긁힐 것으로 예상했다.
• 짜는 것도 별로 어렵지 않아서 빠르게 짰는데, 예제 1이 안나오네? 사실 상당히 큰 가정을 기반으로 한 풀이였다.
• 예제가 안 나온다는 것은 가정이 틀렸다는 거고, 결국 간단하게 고치는 것 자체가 쉽지 않다는 것이다. 똑떨...
• 5번을 열었더니 뭔 이상한 트리가 튀어나와서 바로 걸렀다. 결국 소득 없이 3번으로 돌아왔다.
• 3번의 풀이 자체는 스트링 티피컬 짬뽕 국밥 든든 그 자체여서 빠르게 찾을 수 있었다. 문자열 관련 대비도 꽤 했고.
• 그런데 아무리 생각해도 코드가 300줄 뽑히게 생겨서 마음을 굳게 먹어야 했다. 다행히 이때도 2번 만점자 수가 20명인가 그랬다.
• 3번을 풀면 매우 큰 상을 받을 가능성이 높다고 생각해서, 뇌절하지 말자고 생각하고 짜기 시작했다
• 대충 한 파트 짜고 -> 스코어보드 확인하면서 안도하고 -> 한 파트 짜고 -> 안도하고를 반복
• 다 짰더니 에러가 조금 났는데, 인덱스 실수 하나여서 금방 고쳤다. 예제 나와서 제출했더니 한 방에 맞더라 ㅋㅋ
• 이때가 4시 15분. (3시간 15분 지났을 때) 이제 긁을 것을 찾아서 떠났고 5-1이 긁기 쉽다는 결론을 얻었다.
• 사실 긁기 별로 안 어려운데, 뇌가 극도의 흥분상태여서 뇌절도 꽤 해서 40분 정도 걸렸다. 이때가 5시.
• 4번을 긁으면 진짜 2등상에 못 박는 느낌이어서 무리를 좀 했다. 뚫으려고 별 짓을 다하다가 사망하고 패배를 인정했다. 

문제 풀이

1. 더도 말고 덜도 말고

매우 쉬운 문제. 백준에도 비슷한 문제가 많을 것으로 생각한다. std::map 사용하면 뚝딱.

2. 영원한 휴가

작년 2번에 비해서 상당히 난이도가 올라간 문제. solved.ac 기준 플레 1 ~ 다이아 5 정도라고 개인적으로 생각한다.

$\mathcal{O}(m^2)$ 풀이는 간단한데, 그냥 SCC를 모든 경우에 대해서 다 구해주면 된다. 이러면 섭테 2까지 긁힌다.

본 문제를 해결하려면 SCC를 압축하여 DAG를 만드는 과정을 생각할 필요가 있다. 이제 기존 간선 $u \rightarrow v$를 뒤집었다고 생각하자.

• $u, v$가 같은 SCC에 포함되었다면, 그 간선을 뒤집어서 SCC 크기가 증가하지는 않을 것이다. 그러니 무시해도 된다.
• $u, v$가 다른 SCC에 포함되었다면, DAG 상에서 $u$의 SCC에서 $v$의 SCC로 가는 간선이 있다는 것이다.
• 만약 이 간선을 뒤집는다면, 어떻게 될까? 만약 해당 간선이 $u$의 SCC에서 $v$의 SCC로 가는 유일한 경로라면, 무시해도 된다.
• 하지만 $u$의 SCC에서 $v$의 SCC로 가는 경로가 2개 이상이라면, $u$의 SCC와 $v$의 SCC "사이"에 있는 모든 SCC가 묶인다.
• 여기서 "사이"에 있다는 것은, $u$의 SCC -> ??? -> $v$의 SCC 형태의 경로가 존재하는 ??? 들을 의미한다.

이제 문제를 해결할 수 있다. SCC 압축 DAG를 만든 후, $dp[u][v]$를 $u$번 SCC에서 $v$번 SCC로 가는 경로의 개수가 0개인지, 1개인지, 아니면 2개 이상인지로 정의하자. 이 값은 DAG에서 위상정렬 DP를 하듯이 계산할 수 있으며, 시간복잡도는 $\mathcal{O}(nm)$이다. 이 값을 잘 계산해놓으면 위 관찰을 통해서 답을 얻는 것 역시 쉽게 할 수 있다. 구현을 효율적으로 해야 AC를 얻는다는 말이 있으니, 잘 구현해야한다. $dp$ 계산에서 오버플로우에 주의하자.

3. 회문인 부분 문자열

역시 작년에 비해 매우 어렵다. 다3 정도라고 생각. 복잡한 문제인 만큼 천천히 생각해보자. 해야 하는 것은

• 우선 회문인 부분 문자열을 전부 뽑아낸다.
• 그 중 조건을 만족하는 부분 문자열을 전부 뽑아낸다. (즉, 주어진 회문이 어떤 문자열에 포함되는지 판별해야 한다)
• 그 후, 그 부분 문자열들을 사전순으로 정렬해서 $k$번째 것이 무엇인지를 파악해야 한다.

이제 각 단계를 어떻게 할 수 있을지 생각해보자.

• APIO 2014 팰린드롬의 풀이를 생각하자. 길이 $n$ 문자열의 회문인 서로 다른 부분 문자열의 개수는 최대 $n$개다.
• 이 시점에서 $k$의 제한은 페이크임을 알 수 있다. 또한, 회문을 모두 뽑는 것은 Manacher 알고리즘으로 가능하다.
• 서로 다른 것을 뽑아냈는지를 확인해야 하는데, 이건 Rabin-Karp 해시로 가능하다. 충돌 안하게 모듈로 2개 적당히 잡자.
• 위 koosaga 블로그 링크의 설명을 보면 사실 이 부분을 이분탐색 없이 할 수 있는데, 당시에는 이분탐색까지 덮었다.

이러면 1단계가 끝난다. 여기까지 하고 한 번 예제 넣어서 잘 돌아가는지 확인했다. 이제 2단계.

• 어쨌든 후보들은 "특정 문자열의 부분문자열인 회문"들이다. 이제 이것들이 다른 문자열에도 포함되는지 확인해야 한다.
• 그러면 세 문자열을 합친 (사이에 이상한 문자 껴넣고) 새 문자열을 만든 후, Suffix Array + LCP + Segment Tree를 적용한다.
• 이 과정 자체는 꽤 티피컬한데 구현이 드럽게 힘들고 귀찮다. Suffix Array는 로그제곱으로 짜도 충분하다. 

이러면 2단계가 끝난다. 여기까지 하고 한 번 예제 넣어서 잘 돌아가는지 확인했다. 이제 마지막 단계.

• 이제 부분문자열을 사전순 정렬해야 하는데, 단순하게 Suffix Array 상으로 정렬하면 안된다. (why?)
• 제대로 정렬하려면 "이 회문을 prefix로 갖는 suffix 중 가장 Suffix Array에서 앞에 있는 것"을 찾을 필요가 있다.
• 이를 위해서는 또 한 번 LCP + Segment Tree + 이분탐색을 적용하면 된다. 겁나 귀찮은데 해야함
• 이제 회문들을 "SA 위치, 회문의 길이"라는 pair로 정렬하면 사전순 정렬이 됨을 확인할 수 있다. 끝.

가치가 있다고 생각해서, 디버깅 용 코드까지 전부 그대로 올린다. 

5. 돌 옮기기

5-1을 긁는 것은 어렵지 않다. 상태 전이를 전부 파악하고 union-find를 돌리면 된다.

상태 전이를 효율적으로 하는 게 약간 헷갈릴 수 있는데, 비트마스킹을 잘 활용하면 $\mathcal{O}(n \cdot 2^n)$ 풀이를 얻는다.

뇌절을 한 흔적이 진짜 많이 보이는 코드를 짰다. 알아서 잘 해독하시길 ^~^;;

매우 늦게 올린다. 결과는 6등으로, 예상보다는 매우 높았으나 여전히 만족스러운 결과는 아니었다. J를 풀지 못한것이 아쉬움.

작년의 팀과 멤버는 동일하다. rkm0959, junie, bjwj5505다. 내가 1년간 공부를 많이 한 건 맞지만, 정작 최근에는 CTF 참가 등으로 PS, CP에 집중하지 못해서 팀의 전체적인 실력이 강화된건지 퇴화된건지 좀 애매한 것 같다. 다른 팀원도 비슷하다. 일단 지금까지는 나쁘지 않게 하고 있는듯.

타임라인과 함께 간략한 설명을 붙이도록 하겠다. 모든 사람을 3인칭으로 명명하겠다.

• 시작하자마자 문제 12개 모두 출력
• 스코어보드 보니까 I가 0분컷으로 풀렸네? 진짜 쉽네?
• rkm0959가 바로 컴퓨터 잡고 AC (5분)
• 이때쯤 E도 퍼솔이 나왔고, 바로 rkm0959가 이어서 AC (8분)
• bjwj5505는 이때 L을 읽고 있었고, junie는 앞쪽 문제를 읽는 중.
• bjwj5505가 L을 구현했지만 WA 후 코드 프린트
• rkm0959는 G를 보면서 수학 문제라고 생각을 했으나 매우 어려워보여서 대기중
• 대신 K가 쉽다는 것을 확인하고, 풀이를 bjwj5505와 확인
• rkm0959가 H의 풀이를 찾고, 정당성을 bjwj5505와 확인 
• 그러다가 F가 쉬워보여서 rkm0959, junie가 해결 시도
• bjwj5505가 L을 디버깅하고 있으며, rkm0959가 K를 짜기 시작
• bjwj5505가 L을 고치고 AC (39분), rkm0959도 곧 K AC (46분)
• bjwj5505, junie가 F의 풀이를 찾는동안 rkm0959 H 구현
• F의 풀이를 찾고 AC (51분), H도 곧 AC (58분) - 1시간 6솔브 도달
• 정확하게 기억은 안나지만 junie가 느린 J 풀이를 찾았음 (로그 2개)
• 그러나 정확하게 풀이를 이해하고 있는 사람은 junie 혼자
• bjwj5505, junie는 A의 해결에 집중. rkm0959는 B가 DP임을 확인
• rkm0959가 D가 세그먼트 트리로 해결될 수 있는 문제임을 확인
• A, B, D의 동시다발적 구현 + WA + 디버깅 파티 후 전부 AC (115, 133, 149분)
• J를 고치려고 했고, "맞는" 풀이를 1분 전에 찾았으나 TLE. 똑떨....