베주 항등식 (Bézout's Identity)
두 정수 \(a\)와 \(b\)의 최대공약수를 \(d = \gcd(a, b)\)라고 할 때, 다음 방정식을 만족하는 정수 \(x\)와 \(y\)가 반드시 존재합니다.
\[ax + by = d\]
더 일반적으로 방정식 \(ax + by = c\)를 풀고자 할 때, \(c\)가 \(d\)의 배수가 아니라면 이 방정식은 정수 해를 가질 수 없습니다.
확장 유클리드 알고리즘의 유도
유클리드 호제법을 통해 \(\gcd(a, b)\)를 구하는 과정은 잘 알려져 있습니다. 베주 항등식과 결합하여 생각해보면, \(bx + (a \bmod b)y = d\)라는 방정식은 원래의 방정식과 동일한 해의 구조를 가집니다.
호제법의 마지막 단계인 \(b = 0\)인 경우를 살펴봅시다. 이때 방정식은 \(ax = d\)가 되며, \(a\)는 곧 \(d\)이므로 \(x = 1\), \(y = 0\) (또는 임의의 정수)이 해가 됩니다.
이제 재귀적으로 한 단계씩 올라가며 해를 복원하는 과정을 고려해 봅시다. \(a \bmod b\)는 \(a - \lfloor \frac{a}{b} \rfloor \times b\)로 표현할 수 있으므로, 하위 단계의 방정식은 다음과 같이 변형됩니다.
\[bx + \left(a - \left\lfloor \frac{a}{b} \right\rfloor \times b\right)y = d\]
이를 \(a\)와 \(b\)에 대해 다시 정리하면 다음과 같은 형태가 됩니다.
\[ay + b\left(x - \left\lfloor \frac{a}{b} \right\rfloor y\right) = d\]
하위 단계에서 구한 해를 \((x', y')\)라고 하면, 상위 단계의 해 \((x, y)\)는 다음과 같은 관계를 가집니다.
\[x = y', \quad y = x' - \left\lfloor \frac{a}{b} \right\rfloor y'\]
이를 구현하면 다음과 같습니다.
long long ext_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long next_x, next_y;
long long g = ext_gcd(b, a % b, next_x, next_y);
x = next_y;
y = next_x - (a / b) * next_y;
return g;
}
일반해(General Solution) 도출
위 알고리즘을 통해 구한 \((x_0, y_0)\)는 방정식 \(ax + by = c\)의 특수해 중 하나입니다. 모든 해를 구하기 위해 다음을 가정해 봅시다.
\[a(x_0 + p) + b(y_0 + q) = c\]
이미 \(ax_0 + by_0 = c\)가 성립하므로, 위 식에서 이를 빼면 다음을 얻습니다.
\[ap + bq = 0 \implies p = -\frac{b}{d}k, \quad q = \frac{a}{d}k \quad (k \in \mathbb{Z})\]
따라서 방정식의 일반해는 임의의 정수 \(k\)에 대해 다음과 같이 표현됩니다.
\[\begin{cases} x = x_0 + k \cdot \frac{b}{d} \\ y = y_0 - k \cdot \frac{a}{d} \end{cases}\]
조건을 만족하는 해 구하기
\(x\)와 \(y\)가 모두 양의 정수인 해의 범위, 혹은 그러한 해가 존재하지 않을 때 각각의 최소 양의 정수 해를 구하는 방법을 살펴봅시다.
\(x > 0\) 조건에서 \(k > -x_0 \cdot \frac{d}{b}\) 이어야 하므로, \(k\)의 최솟값은 \(\lfloor -x_0 \cdot \frac{d}{b} \rfloor + 1\)이 됩니다.
마찬가지로 \(y > 0\) 조건에서 \(k < y_0 \cdot \frac{d}{a}\) 이어야 하므로, \(k\)의 최댓값은 \(\lceil y_0 \cdot \frac{d}{a} \rceil - 1\)이 됩니다.
이 두 범위 내에서 유효한 \(k\)가 존재하는지 확인하면 조건을 만족하는 해의 존재 여부와 개수를 알 수 있습니다.
void solve_positive_solutions(long long a, long long b, long long c) {
long long g = std::gcd(a, b);
if (c % g != 0) {
std::cout << -1 << "\n";
return;
}
long long x, y;
ext_gcd(a, b, x, y);
long long multiplier = c / g;
x *= multiplier;
y *= multiplier;
long long step_x = b / g;
long long step_y = a / g;
long long k_min = static_cast<long long>(std::floor(-static_cast<double>(x) / step_x)) + 1;
long long k_max = static_cast<long long>(std::ceil(static_cast<double>(y) / step_y)) - 1;
long long min_x = x + k_min * step_x;
long long max_y = y - k_min * step_y;
long long max_x = x + k_max * step_x;
long long min_y = y - k_max * step_y;
if (min_x > 0 && min_y > 0) {
std::cout << k_max - k_min + 1 << " "
<< min_x << " " << min_y << " "
<< max_x << " " << max_y << "\n";
} else {
std::cout << min_x << " " << max_y << "\n";
}
}