rkm0959

Vertex Simple Cycle을 구성하기 위해서, 왼쪽의 점 몇 개에서 각각 간선 두 개를 선택하는 것을 반복하자.

왼쪽의 점을 순서대로 보면서 사이클을 구축하는데, 이 과정에서 여러 사이클 조각들이 (연결 컴포넌트) 만들어진다.

생각을 해보면 각 컴포넌트들은 어쨌든 완전한 사이클 하나이거나 (이 경우 답에 해당하는 사이클 하나를 얻는다) '일직선' 형태의 컴포넌트가 된다. 

이러한 컴포넌트를 연결하려면 끝점 두 개를 연결해야 한다. 기본적 아이디어는 이게 전부다.

이를 이용하여 동적 계획법을 할 수 있다. $dp[i][j]$는 왼쪽 $i$번째 점까지 고려했을 때, 컴포넌트가 $j$개인 경우의 수다.

식을 세우려고 해보면, 은근 중복 카운팅을 피하기가 어려움을 알 수 있다. 중복 카운팅을 피하기 위해서는 살짝 생각의 방식을 바꿔야 한다.

왼쪽의 점을 순서대로 보면서, 다음을 순서대로 한다고 생각해보자.

1. 이 점에서 '처음으로 도달 가능한' 오른쪽 점들이 있을 것이다. 이 중 사이클에 포함될 점들을 선택한다. 이들은 크기 1의 컴포넌트가 된다. 

2. 만약 그 점을 사이클에 포함할 것이라면, 간선 두 개를 긋는다. 이 두 간선으로 컴포넌트 두 개를 잇는다. 이때, 잇는 점은 컴포넌트의 끝점 중 하나다.

이러면 중복 카운팅이 없어짐을 알 수 있다. 이제 문제는 '컴포넌트의 끝점' 문제다.

컴포넌트의 크기가 1인 경우는, 끝점이 하나 존재하게 된다. 그래서 '컴포넌트의 끝점 두 개를 고르는 방법'에 대한 혼란이 온다.

이를 위해서는 그래프에 방향을 주면 된다. 모든 것을 방향 그래프로 보면, 들어가는 컴포넌트와 나가는 컴포넌트를 고르기면 하면 된다.

이제 컴포넌트의 크기가 1인 경우를 특별히 처리할 이유가 없고, 계산 마지막에 같은 사이클을 두 번 세는 것만 처리하면 된다.

우선 각 tuple에 대해서 게임이 독립적이므로, 각각의 Grundy Number를 구한 다음 XOR 하면 된다.

게임이 굉장히 복잡해보이는데, 사실 이 게임은 단순히 Nimber Multiplication에 대한 게임 해석이다.

그러니 실제로는 각 tuple에 해당하는 Nimber Product를 모두 XOR하면 된다. 

Nimber Field가 characteristic $2$임을 생각하면, 결국 주어진 행렬에서 determinant를 계산하라는 문제가 된다.

Nimber Multiplication이 꽤 시간이 오래 걸려서, 단순하게 가우스 소거를 하면 안되고 적당한 전처리를 해야 한다.

이 전처리의 구체적 내용은 Nimber Multiplication의 기본적 성질을 공부하면 파악할 수 있을 것이다. 찾아보는 것 추천.

RSK Correspondence에 대한 내용을 공부하면 (일단 증명은 공부 안했다 ㅠㅠ) 해결할 수 있다.

내용을 좀 읽다보면 굉장히 도움이 되는 내용을 찾을 수 있고, 그러면 문제를 Young Tableaux에 대한 것으로 바꿀 수 있다.

이제 문제는 Hook Length Formula 및 재귀를 통해서 해결할 수 있다. RSK는 제대로 한 번 봐야할듯.

이런 문제는 기본적으로 행렬로 표현하는 것이 도움이 많이 된다. 

전이행렬을 $M$이라고 하고 초기 확률분포를 $v$라 하면 $k$번의 움직임 후 확률분포는 $M^kv$가 된다.

그러니, 각 타겟에서 시행이 끝날 확률은 단순히 $v + Mv + M^2 v + \cdots $를 계산하여 얻을 수 있다.

수렴성이 보장되므로, $I+M+M^2 + \cdots = (I-M)^{-1}$을 사용할 수 있고, $(I-M)^{-1}v$를 구하면 된다.

이는 식 $(I-M)x = v$를 풀면 얻을 수 있다. 대응되는 matrix가 banded이므로, 효율적으로 가우스 소거를 하면 된다.

각 행에 영향을 주는 행이 위/아래 두 개 뿐이므로, 총 3개의 행에 대한 계수를 각 행에 대하여 저장하면 편하다. 

DP 식 자체는 간단하고, cost 함수인 $\displaystyle \sum_{i=1}^n \left( 1 + \lfloor \log_2 i \rfloor \right)$ 및 실제로 구하고자 하는 값이 $n$에 대하여 볼록함은 쉽게 추측할 수 있고 증명도 수학적 귀납법으로 어렵지 않다. 그런데 $n$ 범위가 $10^{15}$로 매우 높고, 아마도 출제자가 답이 long long int 범위를 넘어가도록 문제를 만들지는 않았을 것이므로, 답이 증가하는 폭이 꽤 작을 것이라고 유추할 수 있다. 즉, 실제로 답의 기울기가 변화하는 점이 적을 것이라고 생각하는 것이다. 이제 기울기가 변화하는 점을 이분탐색/삼분탐색을 잘 섞어서 찾아나가면 된다. 이 아이디어만 잡으면 그 뒤는 어렵지 않은데 아이디어 잡기가 굉장히 어려운 문제인 것 같다.

갓문제. 풀이는 월파 당시 어느 정도 스포를 당해서 100% 내가 생각한 풀이는 아니다. 다음 관찰을 순서대로 한다.

1. 만약 모든 주기가 서로소라면, 중국인의 나머지 정리처럼 생각하면 결국 각 신호등이 독립적이라고 봐도 무방하다.

2. 또한, 기본적으로 두 신호등이 있으면 순수히 그 두 신호등만 봤을 때 결과는 주기의 LCM을 주기로 갖는다.

3. 그러니 한 신호등의 주기가 다른 신호등의 주기의 배수라면, 두 개를 동시에 처리할 수 있다.

4. 조금 더 생각하면, 결과적으로 주기들이 모두 prime power인 경우에 문제를 효율적으로 풀 수 있다.

$T = 2520$이라하면, 각 $1 \le u \le 100$에 대하여 $u/\text{gcd}(u,T)$가 모두 prime power가 된다.

그러니, $t \in \{0, 1, \cdots T-1\}$을 보고, 시간대가 $t \pmod{T}$인 경우만을 생각하자.

이 경우, 각 신호등에 대한 결과의 주기가 위 관찰에 의해서 prime power가 되고, 문제를 효율적으로 풀 수 있다.

이걸 각 $t$에 대해 반복한 다음 결과를 합쳐주면 문제를 해결할 수 있다. $T$를 잡는 아이디어가 미친 것 같다.

박테리아의 위치와 방향을 하나의 노드로 생각하면, 박테리아의 움직임은 일종의 functional graph로 모델링할 수 있다.

이제 한 박테리아가 덫이 놓인 칸을 방문하는 것은, 방향에 따른 총 4개의 노드 중 하나를 방문하는 것과 같다.

박테리아는 각 노드를 아예 방문하지 않거나, 한 번 방문하거나, 첫 방문 후 주기적으로 (사이클의 길이에 따라) 방문하게 된다.

그러니 이 정보를 각 박테리아와 각 4개의 노드에 대해서 계산한 다음, 이를 합쳐주면 된다.

합치는 것은 기본적으로 중국인의 나머지 정리를 활용하되, 한 번 방문하는 경우를 조심하며 처리해야 한다.

또한, 실제 첫 방문 시간이 방문 주기보다 클 수 있다는 점을 유의해야 한다. 여러모로 구현에 조심할 게 많다.

다행히도 제한은 여유가 있어서 넉넉하게, 안전하게 구현해도 0ms AC를 받을 수 있다.

멋진 조합문제. 좌표압축이 굉장히 필요해보이는 문제다. 좌표압축을 하면, 각 구간은 사실상 "같은 성질"을 만족하는 값들로 구성되어 있다.

$dp[x][y]$를 $x$번째 사람까지 선택이 끝났고, 현재 선택한 최댓값이 속하는 구간의 번호가 $y$ 이하인 경우의 수라고 하자.

$x$번째 사람이 선택하지 않는 경우, 현재 선택한 최댓값이 속하는 구간의 번호가 $y$가 아닌 경우는 이전에 처리한 DP 값으로 계산할 수 있다.

이제 남은 건 $x$번째 사람이 선택하고, 선택한 최댓값이 속하는 구간의 번호가 $y$인 경우다.

중복 카운팅을 막는 최적의 방법은, "처음으로 $y$번째 구간에서 값을 선택한 위치"를 고정하는 것이다.

이를 $k$라고 하자. 그러면 우선 $k-1$번째 사람까지 선택한 최댓값은 $y-1$ 이하가 되고, $dp[k-1][y-1]$이 나온다.

또한, $k$번째 사람, $x$번째 사람은 $y$번째 구간에서 값을 선택해야 하며, 나머지는 자유다.

하지만, $k$번째에서 $x$번째 사람들이 선택한 값은 증가수열을 이루어야 한다.

$k$번째부터 $x$번째 사람 중 $y$번째 구간에서 값을 선택할 수 있는 사람의 수를 $t$라 하자. (단, $k, x$번째 사람은 제외)

그러면 이 경우 $k$번째부터 $x$번째 사람이 선택할 수 있는 값의 경우의 수는 얼마가 될까?

우선 $t$명 중 $i$명이 실제로 값을 선택한다고 하자. 그러면 $k, x$를 포함해서 $i+2$개의 값을 골라야 하고, 이들은 증가해야 한다.

$y$번째 구간의 길이가 $L$이라면, 결국 $\displaystyle \sum_{i=0}^t \binom{t}{i} \cdot \binom{L}{i+2}$가 원하는 값이 된다.

이는 Vandermonde's Identity를 생각하면 쉽게 계산된다. $\displaystyle \sum_{i=0}^t \binom{t}{i} \cdot \binom{L}{L-i-2} = \binom{t+L}{L-2} = \binom{t+L}{t+2}$를 얻는다.

$k=x$인 경우를 특별하게 처리해주면, 문제를 해결할 수 있다. 이항 계수는 적당히 잘 계산하자. $\mathcal{O}(N^3)$의 동적계획법이 완성된다. 

생성함수를 이용한다. 생성함수에 대한 식으로 답을 표현하는 게 상당히 귀찮다.

전형적인 포함-배제를 하듯이, 열심히 계수를 맞춰주면 되는데, 결론적으로 이런 식이 나온다. 검증해보자.

그러면 식이 대충 계산 가능한 다항식이 분자에 있고, $(1-x^t)$ 형태의 식이 분모에 있는 형태가 된다.

그런데 $\displaystyle \frac{1}{1-x} = 1+ x+x^2+ \cdots $를 이용하면 분모를 없애고 식 전체를 생성함수로 전개할 수 있다.

조금 머리를 굴리면, 댓글의 말처럼 뒤에 있는 네 개의 항을 $\mathcal{O}(n^3)$으로 단순 계산을 할 수 있음을 확인할 수 있다.

첫 번째 항인 $A(x)^4$가 약간의 문제가 된다. 이 경우 $\sum_{i=1}^n \left( x^{l_i} - x^{r_i+1} \right) $에 곱해지는 값은 $\displaystyle \frac{1}{(1-x)^4} = \sum_{k=0}^\infty \binom{k+3}{3} x^k$이다.

이제 $\displaystyle P(x) = \sum_{i=1}^n \left( x^{l_i} - x^{r_i+1} \right)$라 하고, 다항식 $f$의 $x^t$의 계수를 $[f]_t$라 하자.

우리가 구하고자 하는 값은 $\displaystyle \sum_{i=0}^s [P(x)^4]_i \binom{s-i+3}{3}$이다. 문제는 역시 $P(x)^4$를 구할 여력이 없다는 점이다.

이 문제를 Vandermonde's Identity로 해결할 수 있다. 우선 $\displaystyle [P(x)^4]_i = \sum_{j=0}^i [P(x)^2]_j [P(x)^2]_{i-j}$라고 써보자.

그러면 우리가 계산해야 하는 것은 $\displaystyle \sum_{i=0}^s \sum_{j=0}^i [P(x)^2]_j [P(x)^2]_{i-j} \binom{s-j-(i-j)+3}{3}$이다.

이제 저 이항 계수를 쪼개고 싶다는 게 명확해지고, $\displaystyle \binom{s-j-(i-j)+3}{3} = \sum_{l=0}^3 \binom{3-j}{l} \cdot \binom{s-(i-j)}{3-l}$로 이를 쪼갤 수 있다.

식을 제대로 쪼개고 나면 문제가 크게 어렵지 않다. $P(x)^2$에 대한 정보를 전부 계산하고, 정렬/부분합이면 된다.

은근 상수도 커서 (특히 $\mathcal{O}(n^3)$ 부분이 조금 상수가 크다) 구현을 나름 섬세하게 해야 했다.

이 문제의 핵심 아이디어는, 첫 줄에 대한 press/avoid를 결정하면, 나머지는 전부 자동적으로 결정된다는 것이다.

첫 줄을 모두 결정하면, 두 번째 줄은 첫 줄을 맞춰주기 위해서 자동 결정이고, 세 번째 줄은 두 번째 줄을 맞춰주기 위해서 자동 결정이다.

이를 반복하면, 결국 모든 줄이 자동적으로 결정된다. 이때, 우리의 목표는 이때 마지막 줄이 정확하게 완성되는 것이다.

다른 말로 하면, "가상의 마지막 줄"을 하나 더 추가하고, 이들을 전부 avoid 하는 것이 "자동 결정되도록" 하는 것이다.

어쨌든 이를 전부 식으로 쓰면, $\mathbb{F}_2$ 위의 linear equation을 하나 얻을 수 있다. 

이건 가우스 소거 + bitset으로 쉽게 해결할 수 있고, 답 복원도 위 원리를 파악했다면 쉽게 할 수 있다.

구현 디테일이 조금 귀찮은데, $H > W$가 되도록 직사각형을 돌려줘야 한다. 가우스 소거가 $\mathcal{O}(W^3)$에 작동하기 때문이다.

또한, 기본적으로 각 칸의 press/avoid 여부를 첫 줄의 press/avoid 여부의 선형결합으로 표현하는데, 이 과정에서 토글링이 필요하다.

이 문제에서 조금 더 나아가면 Project Euler 707번을 해결할 수 있다. 물론 더 머리를 써야하는 문제다.

아이디어 3개로 문제를 해결할 수 있고, 다른 풀이들도 대부분 이런 방식으로 생각하는 것 같다.

아이디어 1: Bounding Box의 크기는 한 번의 시행마다 양변의 길이가 2만큼 증가한다. 오류 여부는 상관없다.

아이디어 2: 오류가 없는 경우, 시행 이전에 모습을 복원하는 것은 간단한 DP로 어렵지 않게 할 수 있다.

아이디어 3: 오류가 있는 경우, 위 방식대로 복원을 하면 오류가 어떻게 전파되는가를 그려볼 수 있다.

그림을 실제로 그려보면 오류의 존재 여부 및 오류의 위치를 파악하는 방법을 알 수 있다.

또한, 오류의 위치를 알 때 오류를 수정하는 방법 역시 쉽게 파악할 수 있다. 

만약 오류를 수정해도 여전히 오류가 있다면, 그때는 "시행 이전의 모습" 자체가 없었던 것으로 보면 된다.

이제 남은 건 구현이다. 진짜 재밌고 멋있는 문제라고 생각하고, 17WF 남은 문제도 풀어봐야겠다. 

정말 재밌게 푼 문제다. 깔끔하고 아이디어도 좋은 문제. 이 문제는 풀이만 써놓기엔 좀 애매해서 생각 과정도 적는다.

Part 1: 기본적인 관찰

결국 문제의 statement는 각 문제에 대한 아이디어는 시작 후 $0, 1, \cdots t-1$분 후 중 한 시각에 얻어지고, 각 확률이 $1/t$로 동일하며 이는 문제마다 독립적이라는 것이다. 이는 $p \cdot t^n$이 정수인 이유가 되고, 동시에 이 문제가 확률 문제가 아닌 카운팅 문제임을 시사한다.

Part 2: $n$이 작은 경우 직접 계산

우선 $x_1+x_2+ \cdots + x_n > t$인 경우에 답이 $0$임은 자명하다. $n=1$인 경우 답이 $t-x_1+1$임도 자명하다.

$n=2$인 경우를 열심히 계산했고, (이 계산은 어렵지 않다) $(t-x_1-x_2+1)(t-x_2+2)$를 얻었다. 

이는 문제의 답이 생각보다 간단한 형태를 가질 거라는 믿음을 나한테 줬다. 도움이 꽤 된듯.

Part 3: $n = t$, $x_1 = x_2 = \cdots = x_n = 1$인 경우

예제 2가 이런 경우고, $n=5$였다. 이때 예제 답이 $1296$이었는데, 이건 $6^4$다. 

뭔가 느낌이 쎄해서 $n=2$, $n=3$인 경우를 손으로 계산했는데, 각각 $3^1$, $4^2$가 나왔다.

여기서 나는 답이 $(n+1)^{n-1}$이라고 확신했고, 증명을 고민하기 시작했다. 근데 생각해보니 아는 내용이었다.

이 경우에는 중간에 문제가 바뀌는 걸 고민할 필요가 없다. 시간 안에 아이디어가 공급되는 것만이 중요하다.

각 문제의 아이디어가 나오는 시간을 $t_0, t_1, \cdots , t_{n-1}$이라 하면, 정렬 후 $i$번째 값이 $i$ 이하이면 된다. (0-index) 

이건 Parking Function과 같은 문제고, 예전에 한 번 공부를 했다. 여기서 도움을 정말 많이 받았다.

Parking Function하면 역시 원으로 바꾸고 자리 하나 더 만드는 방법이 너무 강력해서, 이를 사용해보기로 생각했다.

Part 4: $x_1 = x_2 = \cdots = x_n = 1$인 경우

기존 Parking Function에서 한 방식과 마찬가지로, 총 $t$개의 타임슬롯에 하나를 추가하고 이를 원형으로 바꾸자.

정당한 시간 배치가 되려면, 추가된 타임슬롯을 사용하지 않으면 된다. 여전히 문제는 Parking Function과 다르지 않다.

문제 큐에서 대기하고 있는 것을 자리가 차지되어서 다음 자리로 넘어가는 것으로 생각하면 된다.

이제 임의로 각 문제의 아이디어가 생각날 시간을 고르고 (즉, 각 차가 선호하는 자리를 고르고) 그 중 추가된 타임슬롯이 비게 되는 경우를 세자.

전체 경우의 수는 $(t+1)^n$이고, 그 중 $(t-n+1)/(t+1)$ 만큼이 추가된 타임슬롯을 사용하지 않는다. 

여기서 기존 Parking Function에서 사용되는 rotation argument가 그대로 사용된다.

그러니 답은 $(t-n+1)(t+1)^{n-1}$이 된다. 이는 $t=n$인 경우 Part 3의 결과와 모순되지 않는다.

Part 5: 본 문제 해결

이제부터 본 문제를 해결해야 한다. 역시 하나의 타임슬롯을 추가하고 원형으로 문제를 바꿔보자.

역순으로, $n$번째 문제부터 순서대로 타임슬롯을 고른다고 하자.

$n, n-1, \cdots , k+1$번째 문제에 대응이 되는 타임슬롯을 골랐다고 하자.

추가한 각 문제가 (한 문제를 연속된 한 구간동안 잡는다는 조건 때문에) "금지하는" 타임슬롯의 개수를 생각해보자.

조금 생각해보면 실제로 금지하는 타임슬롯의 개수가 특정 값으로 고정된다는 것을 알 수 있다. 경우 나누기가 필요 없다는 뜻.

이제 순서대로 타임슬롯을 골라준 다음, 추가된 타임슬롯을 사용하지 않도록 회전해주면 된다.

여기서 실제로 타임슬롯을 고른다는 것의 의미가 무엇인지 헷갈릴 수 있는데, 이건 잘 생각해보자.

큰 그림은 꽤 뻔하지만, 디테일과 구현이 생각보다 까다로운 문제다.

큰 비트부터 보고, 그리디하게 가능하면 1이 XOR의 결과로 나오도록 하는 것을 반복해야 한다.

목표가 $x \in [a,b]$, $y \in [c,d]$에 대하여 $x \oplus y$의 supremum을 구하는 것이라고 하자.

우선, $a, b, c, d$ 각각에 $2^{-60}$을 곱해서 전부 $1$ 미만의 값이 되도록 하자. 나중에 $2^{60}$을 다시 곱하면 된다.

이제 $2^{-1}$에 해당하는 비트부터 시작해서, 큰 비트부터 차례대로 보자.

$a, b, c, d$가 현재 보고 있는 비트를 갖는지 여부를 $0/1$로 표현해보자.

$0000, 0011, 1100, 1111$의 경우에는 결정권이 없으니, 보고 있는 비트를 제외한 값으로 $a, b, c, d$를 대체한다.

$0001$의 경우에는 이 비트에서 XOR을 1로 만들어야 하므로, $y$의 비트를 $1$로 고정해야 한다. 이는 $c$를 교체하는 것과 같다.

$0100$의 경우에도 마찬가지로, $x$의 비트를 $1$로 고정해야 한다. 이는 $a$를 교체하는 것과 같다.

$1101$의 경우에는 $y$의 비트를 $0$으로 고정해야 하고, 이는 $d$를 교체하는 것과 같다.

$0111$의 경우에는 $x$의 비트를 $0$으로 고정해야 하고, 이는 $b$를 교체하는 것과 같다.

$0101$의 경우는 조금 특수한데, 조금 생각하면 이 경우에는 아예 답이 결정됨을 알 수 있다.

$1.000000$과 $0.1111111$을 XOR하면 사실상 가능한 최대의 값을 뽑아낼 수 있기 때문이라고 생각하면 쉽다.

이제 이를 반복해서 재귀적으로 계산하면 되는데, 문제는 이 과정이 무한히 반복될 수 있다는 것이다.

여기서는 $a, b, c, d$의 이진법 표기의 주기성을 이용하면 된다. 즉, 반복 주기가 되면 그 시점에서 재귀를 끊을 수 있다는 것이다.

이렇게 하면 풀이는 완성되는데, 생각보다 고려해야 할 것도 많고 구현도 힘들다. 디테일은 각자 채워 넣어보자. 

예전에 $\mathcal{O}(n^2)$ 논문이 있길래 이걸 구현해보려다가 뇌절을 심하게 하고 멘탈 나가서 놓은 문제였다.

풀이는 이 블로그에서도 언급한 EGZ 정리의 증명을 이용한다. 우선 합성수인 경우, 문제를 쪼개서 합칠 수 있다.

$n=ab$라 쓰자. 단, $a, b > 1$. $2ab-1$개의 수가 있을 때, $a$에 대한 문제를 여러 번 풀어 합이 $a$의 배수가 되도록 묶인 $2b-1$개의 그룹으로 만들 수 있다. $2a-1$개의 수를 가지고 합이 $a$의 배수인 그룹을 하나 만들고, 사용되지 않은 수를 다시 써먹는 것을 반복하면 된다.

이제 $2b-1$개의 그룹을 가지고 단순히 $b$에 대한 문제를 풀면 된다. 이는 구현이 귀찮지만 어렵지는 않다.

소수인 경우가 문제인데, 이는 여러 방법의 증명이 있다. (내가 좋아하는 것은 Chevalley-Warning) 

여기서는 Cauchy-Davenport 정리를 사용한다. 주어진 수를 정렬하여, $0 \le a_1 \le a_2 \le \cdots \le a_{2p-1} < p$라 하자.

이제 $a_i = a_{i+p-1}$인 $i$가 있다면 $i$부터 $i+p-1$을 전부 택하면 합이 자명하게 $p$의 배수가 된다.

그렇지 않다면, 주어진 수를 $\{a_1\}, \{a_2, a_{p+1}\}, \{a_3, a_{p+2}\}, \cdots, \{a_p, a_{2p-1} \}$로 분할하자.

첫 집합을 제외하면, 각 집합의 크기는 (중복 원소가 없으므로) $2$가 된다. 이제 순서대로 Cauchy-Davenport를 쓰면, 각 집합에서 한 원소를 골라서 $p$의 배수를 만들 수 있음을 얻는다. 이를 knapsack과 같은 방법으로 처리하면 끝. 참 멋진 문제라고 생각한다.

위 문제의 구현을 bitset 등으로 최적화하면 맞는다. 이상한 실수를 하나 해서 시간을 오지게 날렸다.

Online FFT 테크닉을 이용하여 해결할 수 있는 문제다. 여기서는 이 테크닉을 간단하게 설명한다.

배열 $a$가 주어져 있고, 이때 $c_i = \sum_{j=0}^i a_j a_{i-j}$를 구하고 싶다고 하면, 단순히 FFT를 적용하면 된다.

그런데 만약 $a_i$가 $c_i$와 관련된 값이라던가, 배열 $a$가 바로 주어지지 않고 online으로 주어지면 어떻게 될까?

이때는 단순한 FFT로는 해결하기가 어려우나, 분할 정복을 추가하여 해결할 수 있다.

여기서는 설명의 간단함을 위해 $a_0=0$이라고 가정하고, $c_i = \sum_{j=1}^i a_j a_{i-j}$를 계산해야 $a_i$를 얻을 수 있는 구조라고 생각하자. 

카탈란 수의 점화식을 순수하게 FFT 하나로 계산한다고 생각하면 편할 것 같다.

$[L, R)$에 대해서, 문제를 해결하는 재귀함수 $f([L, R))$을 생각해보자. 이때 기본 가정은, 각 $L \le x < R$에 대하여 $a_0, a_1, \cdots, a_{L-1}$의 값을 이미 알고 있으며 각 $L \le t < R$에 대해 $p_L(x)^2 = \left( \sum_{i=0}^{L-1} a_i x^i \right)^2$의 $x^t$ 계수를 저장해놨다고 가정한다.

먼저 $M=(L+R)/2$를 잡고, $f([L, M))$을 호출하자. 이제 $f([M, R))$을 호출할 준비를 해보자.

현재 저장해놓은 $M \le t <R$에 대한 $p_L(x)^2$의 $x^t$의 계수들을 $p_M(x)^2$의 $x^t$의 계수들로 바꿔야 한다.

이는 결국 $(p_M(x)-p_L(x))(p_M(x)+p_L(x))$의 $x^t$ 계수를 구하는 것과 마찬가지다.

$p_M(x)-p_L(x)$는 $L$차 이상 $M$차 미만 단항식들로 구성되어 있다. 또한, 구해야 하는 계수는 최대 $R-1$차이다.

그러니, $p_M(x)+p_L(x)$의 $R-1-L$차 이하 단항식들만 고려해도 충분하다. 그러니 곱해야 하는 두 다항식의 실질적인 차수는 $R-L$에 비례한다. 개인적으로는 $L=0$인 경우를 따로 고려하는 것이 마음이 편하다. 어쨌든 정복 단계라고 볼 수 있는 스텝이 FFT로 $\mathcal{O}((R-L)\log(R-L))$에 된다.

그러니 총 시간복잡도는 $\mathcal{O}(N \log^2 N)$이 된다. 로그 하나는 순수한 분할정복에서 나오므로 꽤 빠르다.

식을 조금만 정리해보면 $x_p$가 굉장히 간단한 형태로 나온다는 것을 알 수 있고, 이를 통해서 $p$의 값의 후보를 얻는다.

답을 구하는 것도 매우 쉬운데, 특별한 시간 제한 때문에 Ruby 2.7 등의 언어를 사용해서 문제를 해결해야 한다.

Ruby 2.7 문법을 배우는 것이 시간이 꽤 오래 걸릴 것 같았는데, 요구하는 연산이 간단해서 다행이다.

각 숫자가 등장하는 위치를 모두 vector로 들고 있으면, 각 사람에게 돌을 추가해야 하는 시점이 언제인지를 빠르게 구할 수 있다. 

물론, 이를 전부 naive하게 계산하면 TLE가 나고, 메모이제이션을 하면서 계산하면 된다. 

즉, 특정 돌 개수에서 특정 턴일 때 몇 개의 돌이 추가되는지를 메모이제이션을 하면서 계산한다. 

상태의 개수가 꽤 작다는 점은 직관적으로 이해하긴 했는데, 가장 쉽고 명확하게 설명할 수 있는 방법이 뭔지는 아직 잘 모르겠다.  

이 문제와 매우 비슷한 형식을 가지고 있는 문제다. 마찬가지로 포함배제를 사용해보자. 편의상 $v_i = b^i - c + 1$이라고 쓴다.

그러면 식이 $\displaystyle \sum_{S \subset \{1,2, \cdots n\}} (-1)^{|S|} \binom{m+n-1-\sum_{i \in S} v_i}{m}$임을 쉽게 확인할 수 있다. 여기까지는 링크의 문제와 같다.

보통 이런 식이 나오면, $\sum_{i \in S} v_i$에 대한 다항식으로 이항계수를 생각하고 싶다.

그런데 여기서는 조합적 해석의 특성상, $a<b$에 대하여 $\binom{a}{b}$를 다항식의 값이 아니라 $0$으로 봐야 한다.

이걸 다루기가 꽤 까다로운데, 앞선 문제에서는 이를 meet in the middle 방식으로 해결했다.

여기서는 $v_i$의 특수한 형식 - 즉 지수적으로 증가하는 형태 - 를 극단적으로 활용할 수 있다.

$dp[i][j][k]$를 $\sum_{S \subset \{1,2, \cdots , i\}, |S|=j} \left( \sum_{t \in S} v_t \right)^k$라고 정의하자. 이는 식을 열심히 전개하여, $\mathcal{O}(m^4)$에 전처리를 할 수 있다. 

이제 $\sum_{i \in S} v_i \le m+n-1$인 집합 $S$에 대해서만 다항식의 합을 계산해야 한다. 이는 Digit DP를 하듯이 계산할 수 있다. 

큰 "비트"부터 내려가면서, 지금까지 뽑은 것을 봤을 때 나머지를 "자유롭게" 뽑을 수 있다면, 전처리한 DP 값을 활용하여 답을 구할 수 있다. 

여기서 $v_i$의 지수적 증가를 활용한다. 전체적으로 문제는 $\mathcal{O}(m^4)$ 시간에 해결되며, 이는 PyPy3으로도 충분히 빠르게 돈다.

$n/2$ 초과 $n$ 이하 소수와 $1$은 쌍을 찾을 수 없고, 나머지는 쌍을 만들 수 있음을 쉽게 확인할 수 있다.

그러니 문제의 답을 구하기 위해서는 $n$ 이하의 소수 개수를 빠르게 계산할 수 있으면 된다.

나는 Lucy-Hedgehog 방식을 사용하는데, 이게 생각보다 꽤 느려서 Meissel-Lehmer를 새로 배웠다.

Codeforces Educational Round에 있는 Four Divisors 문제에서 가장 빠른 코드들을 많이 참고했다. 

Lucy-Hedgehog 방식이 기본적으로 $\mathcal{O}(N^{3/4})$고, 최적화하면 $\mathcal{O}(N^{2/3})$인데 최적화된 버전을 한 번 구현할 필요를 느낀다. 

우선 $x=1$을 따로 처리하고, 양변에 $x-1$을 곱해서 $x^m-1$에 대한 생각을 해보자.

이제부터 $x^m \equiv 1$이라 생각할 수 있으니, 고려해야 하는 다항식을 $m-1$차 다항식으로 변환할 수 있다.

이제 $x^m-1$이 $\sum_{i=0}^{m-1} c_i x^i$의 약수가 되는 $x$를 모두 구해야 한다.

물론, 모든 $c_i$가 $0$이라면 답은 무한하므로 $-1$을 출력해준다.

$x$진법처럼 생각하면, $x > \operatorname{max}|c_i|+2$인 경우 주어진 식은 해를 가지지 않는다.

그러니 각 $x \le \operatorname{max}|c_i|+2$인 경우에 대해서 판별을 빠르게 해주면 된다.

$x$를 고정하면, 다음과 같은 방식으로 다항식을 simplify 하는 아이디어를 생각할 수 있다.

$c_i \ge x$가 있다면, $x \cdot x^i$를 $x^{i+1}$로 바꿔준다. 즉, $c_i$에서 $x$를 빼고 $c_{i+1}$에 $1$을 더한다.

$c_i \le -x$가 있다면, $x \cdot x^i$를 $x^{i+1}$로 바꿔준다. 즉, $c_i$에서 $x$를 더하고 $c_{i+1}$에 $1$을 뺀다.

여기서 $x^m \equiv 1$도 활용한다. 한 번의 simplification에서 $\sum_{i=0}^{m-1} |c_i|$가 $x-1$만큼 감소한다.

초기 $\sum_{i=0}^{m-1} |c_i|$의 값은 $\mathcal{O}(N)$이므로, 이 과정은 $\mathcal{O}(N/x)$번 반복된다.

이제 simplify가 된 상황에서는 판별이 간단하다. 모든 $c_i$가 $0$이거나, $x-1$이거나, $-x+1$이어야 한다.

이 과정을 효율적으로 하려면 std::map, std::set 등을 든든하게 활용하고, 모든 연산을 rollback 하기 위한 stack도 관리해야 한다.

풀이를 내는 것보다 진짜 구현하는 게 훨씬 더 귀찮았던 문제였다. 다행히 시간제한은 여유있는 문제인듯.

이 글에 나온 이상한 공식을 사용한다. 답이 생긴 게 굉장히 resultant 느낌이 나게 생겼다.

또한, 다뤄야 하는 다항식들은 Chebyshev 다항식의 형태를 가질 것을 예측할 수 있다. 

실제로 이 아이디어는 맞고, Chebyshev 다항식이 갖는 다양한 성질들을 이용해서 잘 계산하면 답을 얻는다.

처음에 행렬곱을 생각해 쿼리당 $\mathcal{O}(n^3 \log m)$을 짜서 시간을 좀 많이 날려먹었다. 위 풀이는 쿼리당 $\mathcal{O}(n^2 \log m)$이다.

시간 제한이 워낙에 빡빡해서 Barrett Reduction 등 아는 모든 최적화 방법을 다 동원했다. 진짜 힘들었다....

귀찮고 쉬운 중국인의 나머지 정리 활용문제다. 벽을 기준으로 대칭시켜서 보는 것은 나름 well-known.

구현이 조금 귀찮은 면이 있는데, 이 문제에서는 $a, b$가 음수일 수 있고 서로소가 아닐 수 있음에 특별히 주의할 필요가 있다.

다항식의 거듭제곱을 빠르게 구하는 문제다. $Q = P^n$이면 $Q' = nP^{n-1}P'$이고 $Q'P = nQP'$을 얻는다.

이 식을 전개해보면, $Q$의 각 계수를 $Q$의 이전 계수에 대한 식으로 쓸 수 있음을 확인할 수 있다.

이를 naive 하게 구현하면 충분히 시간 안에 답을 얻을 수 있다. 최근에 관련 코포 글이 하나 올라왔는데 읽어봐야겠음.

감동적으로 좋은 문제. 우선 많은 XOR 문제가 그렇듯이, 비트로 쪼갤 생각을 해야 한다.

$m_1 \ge m_2 \ge \cdots \ge m_n$이라고 하고, $2^t \le m_1 < 2^{t+1}$이 성립한다고 하자. 특히, $m_1$부터 $m_k$가 $2^t$ 이상이고, 나머지는 $2^t$ 미만이라고 하자.

우리는 기본적으로 $2^t$ 비트를 짝수개 뽑아야 한다. $1 \le i \le k$인 $i$에 대하여, $i$번째 변수에서 $2^t$를 뽑는다면 그 변수의 범위는 $2^t$에서 $m_i$가 된다. 

그렇지 않는다면, $i$번째 변수는 $0$부터 $2^t-1$까지를 아무거나 뽑아줄 수 있다. 이는 굉장히 강력한 조건이며 이 문제의 핵심이다.

만약 $1 \le i \le k$ 중 $2^t$를 뽑지 않는 $i$가 있다면, 그 $i$를 제외하고 다른 변수들이 $2^t$ 비트만 제대로 맞춰주면 전체 XOR이 $0$이도록 $i$번째 변수의 값을 유일하게 결정할 수 있기 때문이다. 이를 생각하면, "처음으로 $2^t$를 뽑지 않는 index $i$"를 기준으로 카운팅을 해서 답을 얻을 수 있다.

만약 모든 $1 \le i \le k$에 대하여 $2^t$를 뽑는다면, $k$는 짝수여야 하며, $2^t$ 비트를 모두 제거했다고 가정하고 더 작은 문제를 해결하면 된다. 

가장 직관적인 접근은 역시 "가성비가 좋은 것을 많이 쓰자"다. 물론, 이게 안되니까 문제가 다이아 3이다.

하지만 이 직관은 전체적인 문제 해결에 정말 많은 도움을 준다. 

이 문제의 풀이를 쓰면 매우 길어질 것 같으니, 이미 풀이를 매우 잘 작성해주신 lego0901님의 블로그로 링크를 건다. 

중요한 것은 convex/linear 함수의 최댓값은 양쪽 끝에서만 발생한다는 사실이고, 이를 활용하는 직관이다.

(사실 난 lego0901님처럼 엄밀하게 증명하지 않고 대충 이러면 풀릴 거라고 믿고 짰다 ㅋㅋ)

우선 $N=K$이고 $N$이 홀수인 경우에 답이 없음은 정삼각형의 경우에서 직관적이고 증명하기도 어렵지 않다.

이제 본격적으로 construction을 생각해야 하는데, 같은 길이를 많이 만들어야 하니 $x^2+y^2 = T$의 해의 개수를 생각할 수 밖에 없다.

이는 $T$에 $4k+1$ 꼴 소수를 잔뜩 박아넣으면 되고, 대충 $T=5^4 \cdot 13 \cdot 17 \cdot 29 \cdot 37 \cdot 41 \cdot 53 \cdot 61$을 사용하면 된다.

이제 construction을 위해서는 길이가 $\sqrt{T}$인 벡터들을 몇 가지 모은 뒤, 이들을 각도정렬하여 만들면 된다.

몇 가지 주의사항이 있는데, $N$이 짝수인 경우에는 원점 대칭이 되도록 벡터들을 선택해야 한다.

또한, $N$이 홀수인 경우에는 $N-1$개의 길이가 $\sqrt{T}$이도록 만들면 되는데, 이 벡터들의 합이 $0$이 아니도록 해야 한다.

즉, 전부 원점 대칭이 되면 안된다. 또한, 첫 번째 길이가 $\sqrt{T}$가 되도록 적당히 점들의 순서를 회전할 필요도 있다.

마지막으로, 은근히 빡빡한 조건 중 하나인 좌표 범위 조건을 만족하기 위해 적당한 평행이동을 시켜주도록 하자. 

현재 우리가 아는 것은 $N, e, d$이고, 목표는 $N$의 인수분해이다. 

이제 $k = ed-1$을 계산하면, 이 값은 $\phi(N)$의 배수가 된다. 특히, $\phi(N)$이 짝수이므로 $k$도 짝수다.

이제 $k = 2^t r$이라 쓰자. (단, $r$은 홀수, $t \ge 1$) 이제 다음을 반복한다. 

1. $N$의 배수가 아닌 $g$를 랜덤하게 하나 잡자. 만약 $\text{gcd}(g, N) \neq 1$이면 소인수분해 끝.

2. $0 \le i \le t$에 대하여 $s_i = g^{k/2^i} \pmod{N}$라 하자. $s_{i-1} \equiv s^2_i \equiv 1 \pmod {N}$이고, $s_i \not\equiv \pm 1 \pmod{N}$인 $i$를 찾자.

3. 이때, $\text{gcd}(s_i - 1, N)$은 $N$의 non-trivial한 factor가 된다. 만약 $i$를 찾는데 실패했다면 다시 처음부터 반복.

우선 $t$의 값은 크지 않으며, 거듭제곱과 modulo 연산 역시 빠른 시간에 할 수 있다. GCD 역시 빠른 시간에 할 수 있다.

그러므로 위 알고리즘에서 한 iteration을 하는데 걸리는 시간은 다항식 시간임을 알 수 있다. 

그러니, 우리가 검증해야 하는 것은 위 알고리즘이 성공할 시 정당한 답을 낸다는 것과, 위 알고리즘이 무시하지 못할 확률로 성공한다는 것이다.

먼저 성공할 시 정당한 답을 낸다는 것을 보이자. 만약 $x^2 \equiv 1 \pmod {N}$인데 $x \not\equiv \pm 1 \pmod{N}$이라 하자.

이는 중국인의 나머지 정리에서, $x \equiv 1 \pmod {p}$이고 $x \equiv -1 \pmod{q}$이거나, $x \equiv -1 \pmod{p}$이고 $x \equiv 1 \pmod {q}$라는 것이다. 

당연히 $p=2$나 $q=2$와 같은 경우를 무시해주면, 이것은 결국 $\text{gcd}(x-1, N)$이 $p$ 또는 $q$라는 뜻이다. 

즉, 2번에서 적당한 $i$를 찾았다면, $\text{gcd}(s_i - 1, N)$은 $N$의 non-trivial factor $p$ 또는 $q$가 된다. ok.

이제 위 알고리즘이 무시하지 못할 확률로 성공함을 설명하자. 50% 정도 이상의 확률로 성공함을 보일 수 있다.

$p-1 = 2^A u$, $q-1 = 2^B v$라 쓰고, (단, $u, v$는 홀수) 일반성을 잃지 않고 $A \ge B$라고 가정하자. 

또한, $k = ed-1$은 $\phi(N) = 2^{A+B}uv$의 배수이므로, $2^{A+B+C} uvw$라고 쓰자. (단, $w$는 홀수) 두 가지 케이스를 나누자.

Note: 이 방식으로 케이스를 분류하는 것은 Miller-Rabin Primality Test를 소개한 논문에서도 사용되는 방식이다. 근본 넘친다.

Case 1. $A > B$가 성립한다.

만약 $g$가 $p$에 대한 비이차잉여라면, 성공함을 보인다.

$g^{2^{A-1}u} \equiv -1 \pmod {p}$이므로, $g^{2^{A-1}uvw} \equiv -1 \pmod{p}$이다. 

또한, $g^{2^Bv} \equiv 1 \pmod{q}$이므로, $g^{2^{A-1}uvw} \equiv 1 \pmod{q}$이다. 

여기서 우리는 $g^{2^A uvw} \equiv 1 \pmod {N}$이고, $g^{2^{A-1}uvw}$는 우리가 원하는 형태를 갖춤을 알 수 있다.

$k = 2^{A+B+C} uvw$이니, 위 알고리즘을 사용하면 우리가 원하는 $g^{2^{A-1}uvw}$를 마주치고 소인수분해에 성공한다.

Case 2. $A = B = K$가 성립한다.

만약 $g$의 $N$에 대한 Jacobi Symbol의 값이 $-1$이라면, 성공함을 보인다.

잠시 $g$가 $p$에 대한 비이차잉여이고, $q$에 대한 이차잉여라고 가정하자. 반대인 경우에도 마찬가지이다.

$g^{2^{K-1}u} \equiv -1 \pmod{p}$이고 $g^{2^{K-1}v} \equiv 1 \pmod{q}$이다. 

그러니 $g^{2^{K-1}uvw} \equiv -1 \pmod{p}$이고 $g^{2^{K-1}uvw} \equiv 1 \pmod {q}$가 성립한다. 

여기서 우리는 $g^{2^K uvw} \equiv 1 \pmod {N}$이고, $g^{2^{K-1}uvw}$는 우리가 원하는 형태를 갖춤을 알 수 있다.

$k = 2^{2K+C} uvw$이니, 위 알고리즘을 사용하면 우리가 원하는 $g^{2^{K-1}uvw}$를 마주치고 소인수분해에 성공한다.

두 경우 모두에서, 성공 확률이 50% 이상임을 쉽게 파악할 수 있다. 그러니 이를 충분히 반복하면 인수분해에 성공한다.

앞선 논문 리딩에서도 사용된 연분수를 이용한 rational approximation이 다시 등장한다.

$ed \equiv 1 \pmod{\phi(N)}$이므로, 적당한 $k$가 있어 $ed - k \phi(N) = 1$이다. 그러니, 이를 다시 쓰면 $\displaystyle \left| \frac{e}{\phi(N)} - \frac{k}{d} \right| = \frac{1}{d\phi(N)}$이다.

즉, $\displaystyle \frac{k}{d}$는 $\displaystyle \frac{e}{\phi(N)}$의 근사가 된다. 그런데 $\phi(N)$은 몰라도, $N$은 이미 알고 있다.

또한, $\phi(N) = N -p - q + 1$이고 $p+q-1 < 3 \sqrt{N}$이므로, $|N - \phi(N)| < 3\sqrt{N}$이다.

즉, $\phi(N)$ 대신 $N$을 사용해도 꽤 강력한 근사가 나올 것임을 추측할 수 있다. 

실제로, $\displaystyle \left| \frac{e}{N} - \frac{k}{d} \right| = \left| \frac{ed-k\phi(N) - kN + k \phi(N)}{Nd} \right| = \left| \frac{1-k(N-\phi(N))}{Nd} \right| \le \frac{3k\sqrt{N}}{Nd} = \frac{3k}{d\sqrt{N}}$을 얻는다.

그런데 $k \phi(N) = ed-1 < ed$이고 $e < \phi(N)$이므로 $k < d < \frac{1}{3} N^{1/4}$를 얻는다.

그러므로, $\displaystyle \left| \frac{e}{N} - \frac{k}{d} \right| \le \frac{3k}{d\sqrt{N}} < \frac{1}{dN^{1/4}} < \frac{1}{2d^2}$을 얻는다. 원하는 식이 나왔다. 연분수를 강제하는 형태의 부등식이다.

잘 알려진 연분수 및 근사에 대한 정리에서, $\displaystyle \frac{k}{d}$는 $\displaystyle \frac{e}{N}$의 연분수 표현에서의 근사분수 중 하나다.

또한, 근사분수의 분모의 크기는 지수적으로 증가하며, $\text{gcd}(k, d) =1$이므로 기약분수 여부는 걱정할 필요가 없다.

즉, 실제로 고려해야 할 근사분수의 개수, 즉 $d$의 후보는 다항식 개수만큼 있다. 이를 전부 시도해보면 된다.

후보를 하나 고정하면, $N, e, d, k$를 전부 알 수 있으므로 $\phi(N)$을 계산하는 시도를 할 수 있다.

이제 $\phi(N)$의 값에 대한 후보가 있을 때, 이 값이 $\phi(N)$이 맞는지 판별하는 것은 어렵지 않으므로, (이차방정식 이용) 증명 끝.

문헌을 뒤져보니, 결과적으로 증명 도중에 가정을 꽤 많이 추가해야 하는 것 같다.

별로 중요하지 않아보이나 매우 중요한 사실을 하나 짚고 넘어가자. $d_p \neq d_q$가 성립한다. 

이유는 간단한데, $d_p = d_q$가 성립하면 $\lambda(N) = \text{lcm}(p-1, q-1)$이라 할 때 $d \pmod{\lambda(N)} = d_p = d_q$가 작게 된다.

Wiener's Attack을 간단하게 확장하면, $\phi(N)$ 대신 $\lambda(N)$을 이용하더라도 비슷하게 공격을 할 수 있다. 

물론, $d_p = d_q$가 크면 애초에 이 최적화 방법을 사용할 이유가 없다. 이 정도면 $d_p \neq d_q$를 가정할 근거가 된다.

또한, 아래에서는 $d_p$와 $d_q$가 "정말 다르다"라는 가정을 사용하게 된다. 이 역시 인정하고 넘어가도록 하자.

핵심 아이디어를 소개하기 위해서, $\mathcal{O}(\operatorname{min}(d_p, d_q))$ 시간에 $N$을 소인수분해하는 방법을 제시한다.

0. $\operatorname{min}(d_p, d_q) < B$가 성립한다고 가정하자. adversary는 공격을 시도하기 위해 $B$의 값을 적당히 잡을 수 있다.

1. 랜덤한 자연수 $m$을 하나 잡는다. $m$이 $N$의 배수가 아니도록 한다. $\text{gcd}(m, N) \neq 1$이면 끝.

2. 각 $1 \le i \le B$에 대하여, $\text{gcd}(m^{ei}-m, N)$을 계산하고, non-trivial factor가 나오는지 확인한다.

3. 성공하면 끝이고, 아니면 다시 1번으로 돌아가서 이 과정을 반복한다.  

이 알고리즘이 효율적으로 작동함은 자명하다. 성공 확률이 무시하지 못할 정도임을 증명하면 충분하다.

일반성을 잃지 않고, $d_p < B$가 성립한다고 가정하자. 또한, 운이 좋게 $m$이 $q$의 원시근이 되었다고 가정하자.

그러면 $m^{ed_p} \equiv m \pmod{p}$이고, $m^{ed_p} \not\equiv m \pmod{q}$가 성립하게 된다. 여기서 $ed_p \not\equiv ed_q \equiv 1 \pmod{q-1}$을 이용하였다. 

그러니 $\text{gcd}(m^{ed_p}-m, N)$은 우리가 원하는 non-trivial factor가 되고, $d_p < B$니 이는 알고리즘 중간에 계산이 된다.

또한, 원시근의 개수는 충분히 많다는 것이 잘 알려져 있으므로, $m$이 $q$의 원시근임을 충분히 기대할 수 있다.

물론, 실제로는 $m$이 $q$의 원시근인 조건이 필요조건이 아니므로, 성공할 확률이 더욱 높다고 볼 수 있다.

이제 이를 최적화해보자. Baby-Step-Giant-Step의 변형이 필요해보인다. 그림을 그려보면, 다음과 같다.

0. $\operatorname{min}(d_p, d_q) < B$가 성립한다고 가정하자. $M = \lfloor \sqrt{B} \rfloor$라고 하자. 

1. 랜덤한 자연수 $m$을 하나 잡는다. $m$이 $N$의 배수가 아니도록 한다. $\text{gcd}(m, N) \neq 1$이면 끝.

2. 각 $0 \le i < M$, $0 \le j \le M+1$에 대하여, $\text{gcd}(m^{e(i+jM)}-m, N)$을 계산하고, non-trivial factor가 나오는지 확인한다.

3. 성공하면 끝이고, 아니면 다시 1번으로 돌아가서 이 과정을 반복한다.

물론, 이 알고리즘은 정당하지만 앞서 살펴본 알고리즘과 시간복잡도가 동일하다. 더욱 최적화가 필요하다.

아이디어는, $i$를 고정한 뒤 각 $j$에 대한 확인을 빠르게 하자는 것이다. 이게 가능할까? 가능하다.

0. $\operatorname{min}(d_p, d_q) < B$가 성립한다고 가정하자. $M = \lfloor \sqrt{B} \rfloor$라고 하자. 

1. 랜덤한 자연수 $m$을 하나 잡는다. $m$이 $N$의 배수가 아니도록 한다. $\text{gcd}(m, N) \neq 1$이면 끝.

2. $G(x) = \prod_{j=0}^{M+1} \left( m^{eMj}x - m \right) \pmod{N}$이라 하자. 이는 다항식이다.

3. $G(m^0), G(m^e), \cdots , G(m^{e(M-1)})$을 전부 계산한 다음, 각 값과 $N$ 사이의 GCD를 계산한다. 

4. non-trivial factor를 얻으면 끝이고, 아니면 다시 1번으로 돌아가서 이 과정을 반복한다.

분석을 위해서, 다시 $d_p < B$를 가정하자. 또한, $d_p = d_1 + M d_2$, $0 \le d_1 < M$, $0 \le d_2 \le M+1$이라 하자. $m$이 $q$의 원시근이라고 가정하자.

자명하게, $G(m^{ed_1})$은 $p$의 배수가 된다. 게다가, $d_q$가 $d_1, d_1+M, \cdots , d_1+M(M+1)$과 전부 다르다면, $G(m^{ed_1})$는 $q$의 배수가 되지 않는다. 

그러니 $G(m^{ed_1})$은 $N$과 non-trivial factor를 갖는다. 그러니 위 가정이 전부 성립하면, 알고리즘은 성공한다.

$m$이 $q$의 원시근이 된다는 가정은 앞서 언급했듯이, 원시근의 개수가 많다는 사실에서 기대할만 하다. 

$d_q$가 $d_1, d_1+M, \cdots, d_1+M(M+1)$과 다르다는 가정은 앞서 말한 $d_p$와 $d_q$가 "많이 다르다"는 가정이다.

이는 조금 위험해보이는 가정이지만, 이 정리의 문맥에서는 (즉, CRT를 사용한 RSA의 최적화) 성립하는 가정이라고 한다. 

개인적인 (짧은) 생각으로는 $M$의 값을 적당히 바꿔가면서 알고리즘을 돌려주면 이 가정은 필요가 없을 것 같다. 

그러니 이 알고리즘은 성공할 가능성이 무시하지 못할 정도이다. 그런데 궁금증이 하나 생긴다.

다항식 $G(x)$는 어떻게 효율적으로 계산할 수 있을까? $G(x)$의 값을 $x = m^0 , m^e, \cdots m^{e(M-1)}$에서 어떻게 빠르게 계산할 수 있을까?

이건 PS에서도 보이는 내용이다. FFT + Multipoint Evaluation을 하면 된다. 이는 굳이 여기서 다룰 필요가 없는 내용으로 보인다.

이제 모든 과정을 정리하면, 시간복잡도가 정말 $\mathcal{O}(\operatorname{min}(\sqrt{d_p}, \sqrt{d_q}))$임을 알 수 있다. 증명 끝.

먼저, 각 $g_i$가 전부 최고차항의 계수가 $1$임을 가정할 수 있다. $g_i$의 최고차항의 계수가 $N_i$와 서로소가 아니라면, $N_i$를 소인수분해 할 수 있다. 

이는 RSA를 다루는 우리의 문맥에서 맞지 않다. 이제 $g_i$의 최고차항의 계수의 modulo inverse를 구해서, $g_i$의 최고차항의 계수를 $1$로 바꿀 수 있다.

또한, $M$이 $N_i$들과 서로소가 아닌 경우 역시 RSA를 다루는 우리의 문맥에 맞지 않다. 

그러니, $M$이 $N_i$들과 서로소라고 가정하자. 이러면, $g_i$들에 $x$의 거듭제곱을 적당히 곱해서 모두 차수가 $d$이도록 할 수 있다.

$T_i \equiv \delta_{i, j} \pmod{N_j}$를 만족하는 $T_i$를 CRT로 찾고, $g(x) \equiv \sum_{i=1}^k T_i g_i(x)$를 잡자. $\overline{N} = N_1N_2 \cdots N_k$라 하고, $g(x)$를 $\mathbb{Z}_{\overline{N}}[x]$의 원소로 보자.

$g(x)$의 최고차항의 계수를 각 $i$에 대하여 $\pmod{N_i}$로 보면 $1$임을 확인할 수 있고, 그러니 $g(x)$는 최고차항의 계수가 $1$이다.

또한, $g(x)$의 차수는 $d$이다. 우리가 원하는 $M$은 $g$의 근이며, $M < N_{min} \le \overline{N}^{1/k} < \overline{N}^{1/d}$다.

그러니, $g(x)$와 $\overline{N}$에 대한 Coppersmith's Theorem을 이용하면 $M$을 찾을 수 있다.

아주 특수한 경우를 다루는 만큼, 증명 역시 크게 어렵지 않다. 먼저 $e$와 관련이 없는 큰 그림을 그려보자.

$M_1 \equiv f(M_2) \pmod{N}$을 알고 있으므로, $M_2$는 $g_1(x) = f(x)^e - C_1 \in \mathbb{Z}_N [x]$의 근이다.

또한, $M_2$는 $g_2(x) = x^e - C_2 \in \mathbb{Z}_N [x]$의 근이기도 하다. 즉, $(x-M_2)$는 $g_1(x), g_2(x)$의 공통 약수다.

그러므로, 유클리드 호제법을 이용하여 $g_1(x), g_2(x)$의 최대공약수를 구한 다음, 그 결과가 일차식이라면 $M_2$를 얻을 수 있다.

Note: 조금 생각을 해보면 유클리드 호제법을 하다가 "문제"가 생기면 $N$의 소인수분해를 얻을 수 있다. 이 점 참고.

특히, $e=3$인 경우에는, 최대공약수가 무조건 일차식이 된다. $g_2(x) = x^3 - C_2$를 생각해보자. 

$\text{gcd}(3, \phi(N))=1$이므로, $N=pq$라 할 때 $p, q$는 전부 $2 \pmod{3}$ 형태의 소수이다. 이 경우, $x \rightarrow x^3$은 전단사함수가 된다.

그러므로, $g_2(x) = x^3 - C_2$의 근은 유일하게 존재한다. 즉, $g_2$는 일차식 하나와 irreducible 이차식 하나로 분해된다.

여기서 일차식은 $g_1(x)$와 무조건 공유가 되어야 한다. 공통근이 존재해야 하기 때문이다.

또한, $g_1$과 $g_2$는 서로 나눌 수 없으므로, $g_1$과 $g_2$의 최대공약수는 일차식이 될 수 밖에 없다. 증명 끝.

$e>3$인 경우에는, 최대공약수가 거의 항상 일차식이 되지만, 아닌 경우도 존재한다. 이 경우, 공격은 실패한다.

$g_1(x,y) = x^e - C_1$, $g_2(x, y) = (x+y)^e - C_2$라고 하자. 만약 $y = r_2 - r_1$이라면, 두 다항식은 공통근 $M_1$을 갖는다.

변수가 두 개인 다항식의 공통근이 나왔으므로, Resultant를 생각할 수 있다.

즉, $h(y) = \text{res}_{x} ( g_1, g_2) \in \mathbb{Z}_N [y]$를 계산하면, 이는 $r_2 - r_1$을 근으로 갖는다.

한편, $h$의 차수는 최대 $e^2$이며, $|r_2 - r_1| < 2^m < N^{1/e^2}$이다. 그러니, Coppersmith's Theorem으로 $r_2-r_1$의 값을 구할 수 있다.

이제 $r_2-r_1$의 값을 알면, 남은 문제는 앞서 했던 Franklin-Reiter Related Message Attack으로 해결된다. 증명 끝.

$e, d$의 정의에서, 적당한 자연수 $k$가 있어 $ed-k(N-p-q+1) = 1$이 성립해야 한다.

$d < \phi(N) = N-p-q+1$이 성립하므로, $0< k \le e$가 성립해야 한다. 이제 $q = N/p$라 쓰고 주어진 식을 $\pmod{2^{n/4}}$로 본다.

이제 $edp - kp(N-p+1) + kN \equiv p \pmod{2^{n/4}}$를 얻는다. $e$는 공개되어 있고, $d \pmod{2^{n/4}}$는 이미 알고 있다.

그러니, $ed \pmod{2^{n/4}}$의 값을 이미 알고 있다. 이렇게 되면 위 식은 $k, p$에 대한 합동식이 된다.

특히, 이 식은 $k$를 고정하고 보면 $p$에 대한 이차합동식이 된다. 가능한 $k$의 후보는 $e$개이므로, 각각에 대해서 $p$에 대한 이차합동식을 풀어주자.

이제 $p \pmod{2^{n/4}}$로 가능한 후보를 몇 가지 얻을 수 있고, 각각에 대하여 위 Theorem의 알고리즘을 돌려주면 된다.

이차합동식에 대한 사실들을 잘 조합하면, 가능한 $p$의 후보가 $\mathcal{O}(e \log_2 e)$ 이하임을 알 수 있다고 한다.

그러니, $\mathcal{O}(e \log_2 e)$번의 시도를 하면 $N$의 소인수분해를 얻고 즉 $d$를 계산할 수 있을 것이다.