[Problem] 백준 9267번: A+B

1. 개괄

BOJ의 9267번 문제 "A+B"를 풀이합니다.

 

정확하게 같은 제목을 가지고 있는 문제가 몇 개 있는데, 특히 BOJ의 가장 Well-Known 문제인 #1000 "A+B"가 먼저 떠오르는 제목이었습니다. 그러나 그 난이도는... 뭐 더 이상의 자세한 설명이 필요하겠습니까.

다만, 평소에 정수론을 많이 공부했었던 제 입장에서는 특별히 걸리는 문제는 아니었던 것 같습니다. 한 가지 걸렸던 점은, 오버플로우가 걸릴 가능성이 너무 높아 __int128을 끄집어 써야 했던 상황 정도였던 것 같습니다. Clang 환경을 사용하지 않는 경우(특히 MSVC는 Clang을 기본적으로 지원하지 않는 것으로 악명이 높죠.) 별도의 Clang 컴파일러를 사용하거나 Python을 사용하는 등의 대체제가 있겠습니다.

 

주의: 이 문제는 필자의 글 중 "정수론 심화"에 수록된 "베주 항등식"과 "확장된 유클리드 호제법"에 대한 내용을 알고 있어야 풀이가 가능합니다.

2. 문제 개요

3. 풀이

(1) 관찰

먼저, 문제를 통해 발생하는 현상을 잘 관찰해 봅시다. 각 셀은 $a$와 $b$의 값을 가지고 시작하므로, 종래에는 두 셀이 각각 $x\cdot a+y\cdot b$의 값을 가지게 됩니다. 사실 엄밀히 정리하면, $x$와 $y$는 서로소이긴 한데, 이 부분에 대해서는 잠시 후에 언급하는 걸로 하고, 일단 우리는 두 셀의 값이 $a$와 $b$를 각각 임의의 정수배한 후 합한 값과 동일하다는 것을 확인하면 됩니다.

문제는 지금부터인데, 앞서 간략히 이야기했듯 $x$와 $y$는 서로소이며, 반드시 그래야만 합니다. 그리고, 이 문제가 진행되는 방식을 역방향으로 긁으면 어떤 일이 벌어지는지 눈치챌 수 있다면 이 문제를 풀 수 있습니다. 지금부터, 이 문제에 숨은 나머지 힌트들을 파헤쳐 보도록 합시다.

(2) $x$와 $y$가 서로소일 수밖에 없는 이유

사실 유클리드 호제법을 아주 명쾌하게 이해하고 있다면, 이 부분에 대해서 납득이 어렵지 않을 수 있습니다. 그러나, 이 부분은 문제를 풀어 나가는 과정에서 굉장히 중요한 요소이므로 잠시 짚고 넘어가도록 하겠습니다.

일반적으로 유클리드 호제법은 다음의 아주 단순한 논제를 기반으로 합니다. 일반성을 잃지 않고 $a>b$라고 하죠.

$$\gcd\left(a, b\right)=\gcd\left(a-b, b\right)$$

이 말을 다시 해석하면, 다음과 같은 식 또한 만족한다는 것을 알 수 있습니다.

$$\gcd\left(a, b\right)=\gcd\left(a+b, b\right)$$

즉, 유클리드 호제법의 역연산 또한 대상이 되는 두 수의 최대공약수를 보전합니다. 이를 염두에 두고, 문제의 상황을 다시 보도록 하죠.

현재 우리는 유클리드 호제법의 역연산을 진행하고자 합니다. 그리고 그 두 수는 각각 $a$, $b$이며 각각 $1\cdot a+0\cdot b$와 $0\cdot a+1\cdot b$ 정도로 나타낼 수도 있습니다. 이 과정을 한없이 반복하여 우리는 $ax+by$를 만들어야 합니다.

이 상태에서, 조금 더 생각을 기울여 봅시다. 만약 우리가 현재 계수 쌍이 $\left(x, y\right)$인 상태에 도달했다면, 나머지 한 개의 계수 쌍은 반드시 $\left(x-y, y\right)$이어야 합니다. (또는 $\left(y-x, x\right)$여도 무방합니다.) 즉, 문제의 연산을 통해 새롭게 등장하는 계수 쌍들은 반드시 유클리드 호제법의 역연산의 모양을 띠게 됩니다. 즉, 모든 계수 쌍 $\left(x, y\right)$에 대해 $\gcd\left(x, y\right)$의 값은 반드시 보전됩니다. 그리고, 우리가 만들고자 하는 $a$와 $b$의 계수 쌍 $\left(x, y\right)$은 $\left(1, 0\right)$과 $\left(0, 1\right)$로부터 출발한 계수 쌍이었으므로, $\gcd\left(x, y\right)$의 값은 반드시 1입니다. 즉, 완성되는 모양 $S=ax+by$에 대해, $a$와 $b$의 계수는 반드시 서로수라는 것을 증명할 수 있습니다.

이제 문제를 풀어 나감에 있어 중요한 사실을 알았으니, 실제로 문제를 풀어 보도록 합시다.

(3) 몇 가지 예외 처리

일단 미리 이야기하자면, 우리는 확장된 유클리드 알고리즘을 이용합니다. 이에 대해서는 제 블로그에서 설명한 글이 있으므로 여기서는 자세한 설명은 생략하겠습니다. 간략히 이야기하자면, 다음의 부정방정식의 해를 구하는 과정입니다.

$$ax+by=\gcd\left(a, b\right)$$

그런데, 이 식은 $a$나 $b$가 0인 경우 따위는 상정하지 않습니다. 그렇기 때문에, 몇 가지 예외 사항이 존재하지요. 여기에서 한 술 더 떠서, $S$의 값이 0이 되는 등 정말 다양한 예외 사항들이 존재하는데 Extended Euclide를 적용하기 이전에 이 예외되는 Case들을 먼저 빼내야 합니다. 같은 수준에서 뒤에 등장하는 Case는 앞에 등장하는 Case의 조건을 만족하지 않는다고 가정합니다.

1. $S=0$인 경우: 두 가지 경우가 있습니다.
   • $a>0$이고 $b>0$인 경우: 어떠한 짓을 해도 한쪽 셀에 0을 저장할 수 없습니다. 따라서 반드시 불가능합니다.
   • 이외의 모든 경우: 시작 단계에서 이미 한쪽 셀에 0이 저장되어 있습니다. 따라서 반드시 가능합니다.
2. $a=0$인 경우: b만을 누적 연산하여 $S$를 만들어야 합니다.
   • $b=0$인 경우: 잠시 후 우리는 $S$를 $b$로 나누어 볼 것이기 때문에 예외되는 Case를 미리 제거합니다. 이 경우는 어떠한 짓을 해도 한쪽 셀에 $S$를 저장할 수 없습니다. 따라서 반드시 불가능합니다.
   • $S$가 $b$로 나누어 떨어지지 않는 경우: 어떠한 짓을 해도 한쪽 셀에 $S$를 저장할 수 없습니다. 따라서 반드시 불가능합니다.
   • $S$가 $b$로 나누어 떨어지는 경우: 반드시 $S$를 한쪽 셀에 저장할 수 있음이 보장됩니다. 따라서 반드시 가능합니다.
3. $b=0$인 경우
   • $a=0$인 경우: 잠시 후 우리는 $S$를 $a$로 나누어 볼 것이기 때문에 예외되는 Case를 미리 제거합니다. 이 경우는 어떠한 짓을 해도 한쪽 셀에 $S$를 저장할 수 없습니다. 따라서 반드시 불가능합니다.
   • $S$가 $a$로 나누어 떨어지지 않는 경우: 어떠한 짓을 해도 한쪽 셀에 $S$를 저장할 수 없습니다. 따라서 반드시 불가능합니다.
   • $S$가 $a$로 나누어 떨어지는 경우: 반드시 $S$를 한쪽 셀에 저장할 수 있음이 보장됩니다. 따라서 반드시 가능합니다.
4. $a=S$이거나 $b=S$인 경우: 시작 단계에서 이미 한쪽 셀에 $S$가 저장되어 있습니다. 따라서 반드시 가능합니다.

(4) 일반적인 상황에서의 풀이

이제 거슬리는 Case들은 다 해치웠습니다. (플래그 따위는 올라가지 않으니 안심하십시오.) 지금부터는 일반적인 상황에서 베주 항등식과 확장된 유클리드 호제법을 이용해 문제를 풀어 나갈 예정입니다.

우리는 다음의 방정식을 풀어야 합니다.

$$ax+by=S$$

이제 풀어야 할 식이 정해졌으니, 방정식의 해를 구해 보도록 합시다.

1. 먼저 베주 항등식 $ax+by=d$의 특성 중 하나로, $S$가 $\gcd\left(a, b\right)$의 배수인지 확인해야 합니다. $a$와 $b$가 정해진 이상, 여기에 어떤 자연수를 곱해서 만들어지는 모든 수는 $\gcd\left(a, b\right)$의 배수이기 때문이죠. 만약 이 조건을 만족하지 않는다면 반드시 불가능합니다.
2. 만약 이 조건을 만족한다면, 양변을 $\gcd\left(a, b\right)$로 나누어 방정식을 단순화합니다. 완성된 방정식 $a'x+b'y=S'$에 대해, $\gcd\left(a', b'\right)=1$이므로 문제가 굉장히 단순해집니다.
3. $a'x+b'y=1$을 만족하는 임의의 특수해 한 개를 구합니다. 이 특수해를 $\left(x_0, y_0\right)$라고 합시다. 이제 $\left(x_0S, y_0S\right)$는 $a'x+b'y=S$의 한 특수해이자 $ax+by=S$의 한 특수해가 되었습니다.
4. 정수 $k$에 대해, $\left(x_0S+k\cdot b, y_0S-k\cdot a\right)$는 $ax+by=S$의 일반해가 됨을 알 수 있습니다. 단, 이 일반해의 두 값은 반드시 양의 정수여야 합니다.
5. 일반해의 두 값이 반드시 양의 정수임을 이용하여, 가능한 해 중 $x$의 값이 가장 낮은 해를 구합니다.
6. 일반해의 작동 원리를 이용하여, $x$의 값과 $y$의 값을 조율하여(즉, $x$의 값을 $b$씩 늘리고 $y$의 값을 $a$씩 줄여) $\gcd\left(x, y\right)=1$인 쌍 $\left(x, y\right)$을 구합니다. 만약 $y$가 음수가 되기 전에 이 쌍이 등장하면 정답은 `YES`이고, 모든 해에 대해 이 쌍이 등장하지 않는다면 정답은 `NO`입니다.

이제 모든 풀이가 끝났습니다. 구현은 여러분들에게 맡깁니다.

Tip: 만약 C++을 사용하신다면, `long long`의 값 범위 특성상 Overflow가 발생할 수 있습니다. 이를 감안하여, C++ 구현 시 `__int128`을 사용하셔야 합니다. 단, 이렇게 될 경우 `std::cin`으로 입력을 받을 수 없다는 점은 감안해야 합니다.

4. 소회

얼핏 보기에는 일반적인 정수론 문제인가 싶었는데, 생각보다도 고려할 부분이 많고, 특히 $x$와 $y$가 항상 서로소여야 한다는 것을 증명하는 게 맞물려서 생각보다도 많이 어려웠습니다. 제가 정수론 문제를 엄청나게 많이 풀었었는데도 이게 생각보다 어렵더라구요. 다만, 확장된 유클리드 알고리즘과 베주 항등식이 원래 빈출 주제가 아니다 보니 난이도가 조금 높게 책정된 것 같기도 합니다.

정수론에 자신 있으신 분이라면 한 번쯤 도전해 볼 만한 문제 정도로 간단하게 소회를 끝맺고자 합니다.