9. 유클리드 알고리즘의 활용

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

이 글에서는 다음 4가지 문제를 다룬다. 모두 "유클리드 알고리즘에서 등장한 문제 축소 방식"을 이용한다.

• Lattice Point Counting. $ax+by \le c$, $x, y \ge 1$을 만족하는 격자점 $(x, y)$의 개수를 세는 법.
• Linear Inequality with Modulo. $L \le Ax \pmod{M} \le R$을 만족하는 최소의 음이 아닌 정수 $x$를 구하는 법.
• Modulo Maximization. $1 \le x \le C$이며 $Ax \pmod{M}$이 최댓값이 되도록 하는 $x$를 구하는 법.
• Minimal Fraction. $A/B < x/y < C/D$이며, $y$가 최소인 분수 $x/y$를 찾는 법. 단 $A, C, D \ge 0$, $B \ge 1$.
• 그리고 사실 이 내용에서 중요한 사례라고 볼 수 있는, continued fraction, 연분수를 매우 간단하게 소개한다. 연분수에 대한 내용은 정수론 책을 찾아보거나, 링크에 걸린 글을 읽는 것을 추천. 필자가 연분수에 대한 내용을 직접 소개하기에는 지식이나 엄밀한 이해/직관이 부족한 것 같다. 

Lattice Point Counting

• $ax + by \le c$, $x, y \ge 1$을 만족하는 격자점 $(x, y)$의 개수를 세자. 이를 $(a, b, c)$에 대한 문제라고 부르겠다.
• 일반성을 잃지 않고, $a \ge b$를 가정한다. $a = qb+r$인 $q \ge 1$과 $0 \le r < b$가 존재한다.
• $ax + by \le c$는 $(qb+r)x + by \le c$, 즉 $b(qx+y) + rx \le c$와 같다.
• 그러므로, $bu+rv \le c$이며 $u \ge qv+1$, $v \ge 1$를 만족하는 격자점 $(u, v)$의 개수를 세면 된다. ($x=v$, $y=u-qv$에 대응된다)
• $u$를 고정했을 때 $v \le (c-bu)/r$과 $v \le (u-1)/q$라는 두 부등식이 있다. 둘 중 어느 것이 더 "강한 부등식"인지를 기준으로 경우를 나눈다.
• 계산을 열심히 하면, 그 기준이 $u = \lfloor cq/a \rfloor$임을 알 수 있다. 이제 경우를 나눠보자.

• $u > \lfloor cq/a \rfloor$인 경우, $v \le (c-bu)/r$만 만족하면 된다. 그러니 $bu+rv \le c$만 생각하면 된다.
• $b(u-\lfloor cq/a \rfloor) + rv \le c - b \lfloor cq/a \rfloor$이어야 하며, 원하는 조건은 $u-\lfloor cq/a \rfloor , v \ge 1$이다.
• 이 경우는, 문제를 $(b, r, c - b \lfloor cq/a \rfloor)$에 대한 문제로 축소시켰다.

• $u \le \lfloor cq/a \rfloor$인 경우, $v \le (u-1)/q$만 만족하면 된다. 이 식은 $qv + 1 \le u \le \lfloor cq/a \rfloor$과 같다.
• $v=1$이라면, 가능한 $u$의 개수는 $\lfloor cq/a \rfloor - q$개다. $v$가 $1$ 증가할 때마다, $u$로 가능한 개수가 $q$개 감소한다.
• 결국 이 경우에는, 등차수열의 합으로 가능한 경우의 수를 표현할 수 있다. $\mathcal{O}(1)$ 선으로 정리할 수 있다.

그러니 문제를 유클리드 호제법과 동일한 시간복잡도로 해결할 수 있다. 

$\sum_{k=1}^n \lfloor (a + bk) / c \rfloor$ 형태의 값 역시 같은 알고리즘으로 계산할 수 있다.

• 먼저 $a = qc + r$이면, $\lfloor (a+bk) / c \rfloor = q + \lfloor (r+bk)/c \rfloor$이다. 
• 그러니, $qn$을 값에 더한다음 $a$를 $r$로 바꿀 수 있다. 이제부터 $0 \le a < c$인 경우만 봐도 무방.
• 위 식은 $1 \le x \le n$, $1 \le y$이며 $a+bx \ge cy$인 격자점 $(x, y)$의 개수를 센다.
• 이 식을 변형하여, $cy+b(n+1-x) \le (n+1)b+a$ 형태를 얻는다. 
• $t = n+1-x$라 하면, 목표는 $1 \le t \le n$과 $cy+bt \le (n+1)b + a$다.
• 애초에 $t \ge n+1$일 수 없는게, 그러면 $cy+bt \ge c + b(n+1) > a + b(n+1)$이 성립한다.
• 그러니, 단순히 $cy + bt \le (n+1)b + a$, $y, t \ge 1$인 $(y, t)$의 개수를 세면 끝이다. 즉, $(c, b, (n+1)b+a)$ 문제를 풀자.

Linear Inequality with Modulo

• $L \le Ax \pmod{M} \le R$을 만족하는 최소의 음이 아닌 정수 $x$를 구하는 법을 찾자. 이를 $(A, M, L, R)$ 문제라 하자.
• 먼저 해가 존재하는지 찾자. $Ax \pmod{M}$은 $\text{gcd}(A, M)$의 배수 전체를 표현할 수 있다. (2단원 내용)
• 그러니 $L$과 $R$ 사이에 $\text{gcd}(A, M)$의 배수가 존재하는지만 확인하면 된다. 
• 만약 $L > R$이라면, 구간이 "한 바퀴를 돌았다"고 생각하여, $0$을 문제의 답으로 본다.
• 즉, $[L, R]$이라는 구간을 수평선의 구간으로 보지 말고, 둘레가 $M$인 원의 한 구간으로 보는 것이다.

• 이제 본격적으로 문제를 해결하자. 먼저 $0$이 조건을 만족하는지 확인하자. $L > R$이나 $L=0, R=0$인지 보면 된다. 
• 만약 $2A > M$이라면, $L \le Ax \pmod{M} \le R$과 $M-R \le (M-A)x \pmod{M} \le M-L$이 동치임을 이용하자.
• 이를 사용하면, 문제를 $(M-A, M, M-R, M-L)$ 문제로 옮길 수 있다. 이제 $2(M-A) < M$이다. 이제부터 $2A \le M$을 가정한다.
• 만약 $L \le Ax \le R$인 (단, $L, R$ 모두 $[0, M)$에 속한다. $Ax$는 $M$으로 나눈 나머지로 보지 않는다.) $x$가 있다면, 그 중 가장 작은 것을 반환하자.

• 그렇지 않다는 것은, 일단 $At < L \le R < A(t+1)$인 음이 아닌 정수 $t$가 있음을 의미하고, $R-L+1 < A$임을 얻는다. 이제 진짜 시작. 
• $L \le Ax \pmod{M} \le R$인 최소 $x$를 찾는 건, $L + My \le Ax \le R + My$인 정수 $x$가 있도록 하는 최소 음이 아닌 정수 $y$를 찾는 것이다.
• 이는 다시 $L \le Ax- My \le R$과 같은데, 이걸 $\pmod{A}$로 보면 $L \pmod{A} \le (-My) \pmod{A} \le R \pmod{A}$이다.
• 그러니 $y$의 값을 구하기 위해서는 $(- M \pmod{A}, A, L \pmod{A}, R \pmod{A})$ 문제를 풀어야한다.
• $y$의 값을 구하면, $x$의 값을 구하기 위해서는 단순히 $L + My \le Ax$인 최소의 $x$를 찾기만 하면 된다.

우리는 modulus에 해당하는 값을 $M$에서 $A$로 줄였으며, $2A \le M$이니 이는 최소 반 줄인 것이다. 그러니 로그 시간.

• 최소의 음이 아닌 정수 $x$가 아니라, $T$ 이상의 정수 $x$로 조건을 바꿔도 해결할 수 있다.
• 이 경우, $x = y + T$라고 쓰고 조건을 $(L-AT) \pmod{M} \le Ay \pmod{M} \le (R-AT) \pmod{M}$이라 바꾸자.
• 이제 위 조건을 만족하는 최소의 음이 아닌 정수 $y$를 구한 뒤, $x = y+T$를 대입하면 끝이다.
• 이를 반복하면, $L \le Ax \pmod{M} \le R$을 만족하는 자연수 $x$를 순서대로 나열할 수도 있다.

Modulo Maximization/Minimization

• $1 \le x \le C$를 만족시키면서 $Ax \pmod{M}$이 최댓값이 되도록 하는 $x$를 구하자. 이를 MAX-$(A, M, C)$ 문제라 하자.
• $1 \le x \le C$를 만족시키면서 $Ax \pmod{M}$이 최솟값이 되도록 하는 $x$를 구하자. 이를 MIN-$(A, M, C)$ 문제라 하자.
• MAX 문제나 MIN 문제나 사실 같은 문제다. $A$를 $-A$로 바꿔서 생각하면 두 문제가 같은 문제가 되기 때문이다.
• 이 문제는 "Linear Inequality with Modulo" 문제에 이분탐색을 추가해서 풀 수 있다.
• adamant의 블로그 글이 시각화도 좋고, 설명도 좋고, 추가할 점도 특별히 없는 것 같다. 링크를 거는 것으로 대체한다.
• 그런 줄 알았는데, 실제로 코드를 비교해보니 약간의 문제가 있는 것으로 보인다. 일단은 링크의 아이디어만 알아두자.

Minimal Fraction

• $A/B < x/y < C/D$를 만족시키면서, $y$가 최소인 분수 $x/y$를 찾는 경우. 이를 $(A, B, C, D)$ 문제라 하자.
• 위에서도 언급했지만, $A, C, D \ge 0$, $B \ge 1$을 가정한다. 우리의 목표 $x, y$ 역시 음이 아닌 정수여야 한다.
• 사실 $y$를 최소화하는 것이나 $x$를 최소화하는 것이나 큰 차이가 없다. $y$가 결정되었다면, $Ay/B < x < Cy/B$인 최소의 $x$를 잡으면 된다. 
• $y$가 커지면, 자연스럽게 가능한 $x$의 범위도 "오른쪽으로" 이동하게 될 것이다.
• $D=0$인 경우, $C/D$를 $\infty$로 간주하도록 하겠다. 이 경우까지 처리해야 문제가 풀린다.
• 이 문제는 아래에 언급할 Stern-Brocot Tree를 이용한 풀이가 있다. 링크가 걸린 myungwoo님의 글을 참고하라.

• $A/B < C/D$가 성립하지 않는 경우, 답은 당연히 없고, 이 결과를 반환한다.
• $A=0$인 경우. 이때는 $0 < x/y < C/D$인 것만 생각하면 된다. $x=1$로 고정하고, $1/y < C/D$인 최소의 $y$를 잡으면 ok.
• $A/B$와 $C/D$ 사이에 (양 끝 제외) 정수가 존재하는 경우. $y=1$을 정하고 $x$를 존재하는 정수 중 가장 작은 것으로 잡으면 ok.
• $C/D$가 정수인 경우. 이때, $C/D=n$이라 하자. 이 경우, $A/B < n-1/y$인 최소 $y$를 잡고, $Ay/B < x < ny$인 최소 $x$를 잡으면 ok.
• 이제 $n \le A/B < C/D < n+1$인 자연수 $n$이 존재하는 경우만 남았다. 이 단계가 핵심.
• 목표는 $A/B < x/y < C/D$인 최소 $x, y$를 찾는 것이다. $n$을 빼준 다음, 전부 역수를 취해주자.
• 이제 목표는 $D/(C-nD) < y/(x-ny) < B/(A-nB)$인 최소의 $x,  y$를 찾는 것이다.
• 애초에 분모를 최소화하는 것이나 분자를 최소화하는 것이나 같은 문제이므로, $(D, C-nD, B, A-nB)$ 문제를 풀면 된다.
• 여기서 $n$이 $A, C$를 $B, D$로 나눈 몫임을 생각하면, 이 과정이 유클리드 호제법과 같음을 알 수 있다. 끝. 

관련 문제로 Google Code Jam 2019 Round 2 C번 문제가 있다. 아래 myungwoo님의 글도 그 당시 나왔다.

Continued Fraction

• $[a_0 ; a_1, \cdots , a_k] = a_0 + (1 / (a_1 + (1 / (a_2 + \cdots ) ) ) ) $라고 정의하자. 이를 연분수라고 부른다.
• 모든 유리수는 유한한 연분수로 나타낼 수 있다. $a=qb+r$이라 하면, $a/b = q + r/b = q + 1/(b/r)$이다.
• 이는 $(a, b)$에 대한 문제를 $(b, r)$에 대한 문제로 줄인 것과 같다. 유클리드 호제법 그 자체...
• 연분수는 정말 다양한 성질들이 있다. 이는 학부 정수론 책을 참고하는 것을 추천.
• 또한, 위에서도 언급한 adamant의 Codeforces 블로그를 참고하는 것을 추천한다. 좋은 자료가 많다.
• 연분수와 밀접한 연관이 있는 개념으로 Stern-Brocot Tree가 있다. 이에 대한 글은 myungwoo님의 이 글을 참고하라. 
• 위 링크에서도 나와있지만, Stern-Brocot Tree로 유리수에서 효율적인 이분탐색을 하는 등 매우 흥미로운 알고리즘들이 많다.