선형 디오판토스 방정식¶
(두 변수에 대한) 선형 디오판토스 방정식은 다음과 같은 일반형의 방정식입니다:
여기서 $a$, $b$, $c$는 주어진 정수이고, $x$, $y$는 미지의 정수입니다.
이 글에서는 이러한 방정식에 대한 몇 가지 고전적인 문제를 다룹니다:
- 해 하나 구하기
- 모든 해 구하기
- 주어진 구간 안에 있는 해의 개수와 그 해들 구하기
- $x + y$의 값이 최소인 해 구하기
퇴화된 경우¶
따로 처리해야 하는 퇴화된 경우는 $a = b = 0$일 때입니다. 이 경우 $c = 0$인지 아닌지에 따라 해가 없거나 해가 무수히 많다는 것을 쉽게 알 수 있습니다. 이 글의 나머지 부분에서는 이 경우를 무시하겠습니다.
해석적 풀이¶
$a \neq 0$이고 $b \neq 0$일 때, 방정식 $ax+by=c$는 다음 중 어느 쪽과도 동치로 다룰 수 있습니다:
일반성을 잃지 않고 $b \neq 0$이라고 가정하고 첫 번째 방정식을 살펴봅시다. $a$와 $b$가 서로소일 때, 이 방정식의 해는 다음과 같이 주어집니다.
여기서 $a^{-1}$은 $b$를 법으로 하는 $a$의 모듈러 역원입니다.
$a$와 $b$가 서로소가 아닐 때, 모든 정수 $x$에 대해 $b$를 법으로 한 $ax$의 값은 $g=\gcd(a, b)$로 나누어떨어지므로, 해는 $c$가 $g$로 나누어떨어질 때에만 존재합니다. 이 경우 방정식을 $g$로 나누어 해 중 하나를 구할 수 있습니다:
$g$의 정의에 의해 $a/g$와 $b/g$는 서로소이므로, 해는 다음과 같이 명시적으로 주어집니다.
알고리즘적 풀이¶
베주 보조정리(베주 항등식이라고도 합니다)는 다음 풀이를 이해하는 데 도움이 되는 유용한 결과입니다.
$g = \gcd(a,b)$라고 합시다. 그러면 $ax + by = g$를 만족하는 정수 $x,y$가 존재합니다.
또한 $g$는 $ax + by$ 꼴로 나타낼 수 있는 가장 작은 양의 정수이며, $ax + by$ 꼴의 모든 정수는 $g$의 배수입니다.
미지수가 2개인 디오판토스 방정식의 해 하나를 구하려면 확장 유클리드 알고리즘을 사용하면 됩니다. 먼저 $a$와 $b$가 음이 아니라고 가정합시다. $a$와 $b$에 확장 유클리드 알고리즘을 적용하면, 두 수의 최대공약수 $g$와 다음을 만족하는 두 수 $x_g$, $y_g$를 구할 수 있습니다:
$c$가 $g = \gcd(a, b)$로 나누어떨어지면 주어진 디오판토스 방정식은 해를 가지며, 그렇지 않으면 해를 갖지 않습니다. 증명은 간단합니다: 두 수의 선형 결합은 두 수의 공약수로 나누어떨어집니다.
이제 $c$가 $g$로 나누어떨어진다고 가정하면, 다음을 얻습니다:
따라서 디오판토스 방정식의 해 중 하나는 다음과 같습니다:
위의 아이디어는 $a$나 $b$ 중 하나 또는 둘 다 음수인 경우에도 여전히 성립합니다. 필요한 경우 $x_0$과 $y_0$의 부호만 바꾸면 됩니다.
마지막으로, 이 아이디어를 다음과 같이 구현할 수 있습니다(이 코드는 $a = b = 0$인 경우를 고려하지 않는다는 점에 유의하십시오):
int gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
g = gcd(abs(a), abs(b), x0, y0);
if (c % g) {
return false;
}
x0 *= c / g;
y0 *= c / g;
if (a < 0) x0 = -x0;
if (b < 0) y0 = -y0;
return true;
}
모든 해 구하기¶
하나의 해 $(x_0, y_0)$로부터 주어진 방정식의 모든 해를 얻을 수 있습니다.
$g = \gcd(a, b)$라 하고, $x_0, y_0$을 다음을 만족하는 정수라 합시다:
이제 $x_0$에 $b / g$를 더하는 동시에 $y_0$에서 $a / g$를 빼도 등식이 깨지지 않는다는 것을 알 수 있습니다:
당연히 이 과정은 계속 반복할 수 있으므로, 다음 형태의 모든 수는:
주어진 디오판토스 방정식의 해입니다.
방정식이 선형이므로 모든 해는 같은 직선 위에 있으며, $g$의 정의에 의해 이것이 주어진 디오판토스 방정식의 가능한 모든 해의 집합입니다.
해의 개수 및 주어진 구간 내의 해 구하기¶
앞 절에서 보았듯이, 해에 아무런 제약도 두지 않으면 해가 무한히 많다는 것이 분명합니다. 따라서 이 절에서는 $x$와 $y$의 구간에 몇 가지 제약을 추가하고, 모든 해의 개수를 세고 이를 나열해 보겠습니다.
두 구간 $[min_x; max_x]$와 $[min_y; max_y]$가 있고, 이 두 구간 안에 있는 해만 찾고자 한다고 합시다.
$a$나 $b$가 $0$이면 문제의 해는 하나뿐이라는 점에 유의하십시오. 여기서는 이 경우를 고려하지 않습니다.
먼저, $x \ge min_x$를 만족하면서 $x$의 값이 최소인 해를 찾을 수 있습니다. 이를 위해 먼저 디오판토스 방정식의 임의의 해를 하나 찾습니다. 그런 다음 (앞 절에서 알아본 모든 해의 집합에 관한 내용을 이용하여) 이 해를 이동시켜 $x \ge min_x$가 되도록 합니다. 이는 $O(1)$에 수행할 수 있습니다. 이 $x$의 최솟값을 $l_{x1}$로 나타냅니다.
마찬가지로, $x \le max_x$를 만족하는 $x$의 최댓값을 찾을 수 있습니다. 이 $x$의 최댓값을 $r_{x1}$로 나타냅니다.
마찬가지로, $y$의 최솟값 $(y \ge min_y)$과 $y$의 최댓값 $(y \le max_y)$을 찾을 수 있습니다. 이에 대응하는 $x$의 값을 각각 $l_{x2}$와 $r_{x2}$로 나타냅니다.
최종 해는 x가 $[l_{x1}, r_{x1}]$과 $[l_{x2}, r_{x2}]$의 교집합에 속하는 모든 해입니다. 이 교집합을 $[l_x, r_x]$로 나타냅시다.
다음은 이 아이디어를 구현한 코드입니다. 처음에 $a$와 $b$를 $g$로 나눈다는 점에 주목하십시오. 방정식 $a x + b y = c$는 방정식 $\frac{a}{g} x + \frac{b}{g} y = \frac{c}{g}$와 동치이므로, 대신 이 방정식을 사용하면 $\gcd(\frac{a}{g}, \frac{b}{g}) = 1$이 되어 식이 간단해집니다.
void shift_solution(int & x, int & y, int a, int b, int cnt) {
x += cnt * b;
y -= cnt * a;
}
int find_all_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) {
int x, y, g;
if (!find_any_solution(a, b, c, x, y, g))
return 0;
a /= g;
b /= g;
int sign_a = a > 0 ? +1 : -1;
int sign_b = b > 0 ? +1 : -1;
shift_solution(x, y, a, b, (minx - x) / b);
if (x < minx)
shift_solution(x, y, a, b, sign_b);
if (x > maxx)
return 0;
int lx1 = x;
shift_solution(x, y, a, b, (maxx - x) / b);
if (x > maxx)
shift_solution(x, y, a, b, -sign_b);
int rx1 = x;
shift_solution(x, y, a, b, -(miny - y) / a);
if (y < miny)
shift_solution(x, y, a, b, -sign_a);
if (y > maxy)
return 0;
int lx2 = x;
shift_solution(x, y, a, b, -(maxy - y) / a);
if (y > maxy)
shift_solution(x, y, a, b, sign_a);
int rx2 = x;
if (lx2 > rx2)
swap(lx2, rx2);
int lx = max(lx1, lx2);
int rx = min(rx1, rx2);
if (lx > rx)
return 0;
return (rx - lx) / abs(b) + 1;
}
$l_x$와 $r_x$를 구하고 나면 모든 해를 나열하는 것도 간단합니다. 모든 $k \ge 0$에 대해 $x = r_x$가 될 때까지 $x = l_x + k \cdot \frac{b}{g}$를 순회하면서, 방정식 $a x + b y = c$를 이용해 대응하는 $y$ 값을 구하기만 하면 됩니다.
$x + y$의 값이 최소인 해 구하기¶
여기서도 $x$와 $y$에 어떤 제약 조건을 주어야 합니다. 그렇지 않으면 답이 음의 무한대가 될 수 있습니다.
아이디어는 앞 절과 비슷합니다. 디오판토스 방정식의 해를 아무것이나 하나 구한 다음, 몇 가지 조건을 만족하도록 해를 이동시킵니다.
마지막으로, 모든 해의 집합에 대한 지식을 이용하여 최솟값을 구합니다:
$x + y$는 다음과 같이 변한다는 점에 유의하십시오:
$a < b$이면 가능한 가장 작은 $k$ 값을 선택해야 합니다. $a > b$이면 가능한 가장 큰 $k$ 값을 선택해야 합니다. $a = b$이면 모든 해의 합 $x + y$가 같습니다.