[알고개념] 3. 유클리드 호제법
1. 유클리드 호제법
두 수 m, n의 최대공약수 GCD(m, n) 를 구할 때 사용하는 알고리즘으로, 실제 계산기에도 이 알고리즘을 이용하여 구현되어 있다고 한다. 유클리드 호제법은 다음과 같이 작성할 수 있다.
- a를 b로 나눈 몫과 나머지를 각각 매개변수로 갖는 GCD 함수를 다시 호출한다.
- a를 b로 나눈 나머지가 0이면 b를 답으로 리턴한다.
int GCD(a, b) {
if (a % b == 0) return b;
return GCD(b, a % b);
}이 때 a와 b의 대소관계는 따질 필요가 없다. a가 b보다 항상 커야 할 것 같지만 b가 a보다 클 경우 자동으로 GCD(a, b)를 호출하기 때문이다.
2. 유클리드 호제법의 역산
두 수 x, y에 대하여 GCD(x, y)를 구하는 유클리드 호제법을 역산하면 GCD(x, y)를 x와 y의 일차결합 형태로 작성할 수 있다. 즉, gcd(x, y) == ax + by 에서 a, b의 값을 항상 구할 수 있다.
432와 132의 최대공약수는 12인데, 12는 유클리드 호제법을 역산하면 $4 \times 432\ -\ 13 \times 132$ 형태로 나타낼 수 있다. 위의 사실을 활용하면 정수 계수 방정식 (Diophantine Equation) ax + by = c 이 정수해를 가질 필요충분조건은 $gcd(a, b) | c$ 임을 알 수 있다. 또한 ax + by로 표현되는 가장 작은 양의 정수는 gcd(a, b)이다.
3. ax + by = c의 일반해 구하기
$d = gcd(a,b)$라 하자.
먼저 유클리드 호제법을 이용하여 a와 b의 최대공약수 d를 구한다. 유클리드 호제법을 역산하여 d를 a와 b의 일차결합 형태로 나타낸다. 이 때의 특수해를 $x_1, y_1$ 이라 하자.
$ax + by = c$와 $ax_1 + by_1 = c$를 연립하여 $a(x - x_1) + b(y - y_1) = 0$ 의 식을 구하고, 이 식의 양변에 d를 나누자.
$$\frac{a}{d} (x - x_1) = -\frac{b}{d} (y - y_1)$$
위 식의 $\frac{a}{d}$ 와 $\frac{b}{d}$ 는 서로소이므로, ${a \over d}$는 $y- y_1$을 나눠야 한다. 따라서 $y-y_1 = \frac{ka}{d}$ 이고, $x-x_1 = -\frac{kb}{d}$ 이다. 일반해로 다시 쓰면 아래와 같다.
$$ x = x_1 - \frac{kb}{d},\ \ y = y_1 + \frac{ka}{d} \ (k \in \mathbb{Z})$$
이를 이용하여 백준 11661번. 해의 개수 https://www.acmicpc.net/problem/11661 문제를 풀 수 있다. 난이도가 플래티넘1 이라 좀 많이 어렵지만 위의 과정을 잘 구현하고 예외 케이스만 잘 구별하면 된다.
- GCD 함수는 위와 동일하다. 여기서 연산과정을 저장하기 위해 vec에 유클리드 호제법 순서를 저장하였다.
- reverseEuclidean 함수는 유클리드 호제법 역산을 통하여 GCD를 a와 b의 일차결합으로 나타내는 과정이다. 재귀 코드 한 줄로 위의 역산 과정이 이루어진다.
- 이후 일반해를 구해서 범위에 따라 잘 구별해주면 된다.
- 예외 케이스: a와 b가 0인 경우, 음수인 경우만 잘 파악하면 된다.
#include <bits/stdc++.h>
using namespace std;
vector<long long> vec;
// GCD를 a와 b의 일차결합으로 표현하여 반환 (ax + by = d의 특수해 반환)
pair<long long, long long> reverseEuclidean(int cnt, long long a, long long x, long long b, long long y) {
if (cnt >= vec.size()) return make_pair(x, y);
return reverseEuclidean(cnt + 1, b, y + (-vec[cnt] / vec[cnt - 1]) * x, vec[cnt], x);
}
long long GCD(long long a, long long b) {
vec.push_back(a);
if (a % b == 0) return b;
return GCD(b, a % b);
}
int main() {
cin.tie(NULL); cout.tie(NULL); std::ios::sync_with_stdio(false);
long long a, b, c, d, x1, x2, y1, y2;
long long xs, ys;
// xs, ys: ax + by = gcd의 특수해
cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2;
// 음수 처리: ax => (-a) (-x) 꼴로 변경
if (a < 0) {
a = -a;
long long tp = x2; x2 = -x1; x1 = -tp;
}
if (b < 0) {
b = -b;
long long tp = y2; y2 = -y1; y1 = -tp;
}
// Case 1. a와 b가 모두 0이면 c에 따라 무한 / 0개
if (a == 0 && b == 0) {
if (c == 0) cout << (abs(x2 - x1) + 1) * (abs(y2 - y1) + 1);
else cout << 0;
return 0;
}
// Case 2. a와 b 중 하나가 0이면 나머지 한쪽에만 맞춰서 답 생성
if (a == 0) {
if (abs(c) % b == 0 && (c / b >= y1 && c / b <= y2)) cout << abs(x2 - x1) + 1;
else cout << 0;
return 0;
}
else if (b == 0) {
if (abs(c) % a == 0 && (c / a >= x1 && c / a <= x2)) cout << abs(y2 - y1) + 1;
else cout << 0;
return 0;
}
// Case 3. a와 b가 모두 0이 아닐 경우
d = GCD(a, b);
if (abs(c) % d != 0) { // 정수해를 가질 조건: d | c
cout << 0; return 0;
}
// Case 4. a와 b중 하나 이상이 d인 경우
if (a == d && b == d) {
xs = 1; ys = 0;
}
else if (b == d) {
ys = 1; xs = 0;
}
else {
reverse(vec.begin(), vec.end());
pair<long long, long long> specialSolution = reverseEuclidean(2, vec[0], -vec[1] / vec[0], vec[1], 1);
xs = specialSolution.first;
ys = specialSolution.second;
if (a * xs + b * ys != d) {
long long tp = ys;
ys = xs; xs = tp;
}
if (a * xs + b * ys != d) {
cout << 0; return 0;
}
}
xs *= -c / d;
ys *= -c / d;
long long x_lowk, x_highk, y_lowk, y_highk;
long long bd = -b / d, ad = a / d;
x_lowk = ceil((xs - x2) / (double) -bd);
x_highk = floor((xs - x1) / (double)-bd);
y_lowk = ceil((y1 - ys) / (double)ad);
y_highk = floor((y2 - ys) / (double)ad);
if (x_lowk > x_highk || y_lowk > y_highk
|| y_lowk > x_highk || x_lowk > y_highk) cout << 0;
else cout << min(x_highk, y_highk) - max(x_lowk, y_lowk) + 1;
}