[PS] 백준 #11661. 해의 개수

문제 정보

• 난이도: 플래티넘 I
• 문제 주소: https://www.acmicpc.net/problem/11661
• 이 문제를 푼 이유: 알고리즘 스터디 - 유클리드 호제법

 

문제

방정식 Ax + By + C = 0의 해의 개수를 구하는 프로그램을 작성하시오.

A, B, C, x, y는 모두 정수이고, x1 ≤ x ≤ x2, y1 ≤ y ≤ y2인 해의 개수를 구해야 한다.

 

나의 풀이

자세한 개념은 https://pongkijoa.tistory.com/91 이 글에 작성해두었다. 

$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})$$

 

• 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;
}