UVa OJ 12775 - Gift Dilemma

https://uva.onlinejudge.org/external/127/12775.pdf

\(0 < A, B, C, P < 10^8\)

\(C / gcd(A, B, C) >= 200\)

일 때,

Ax + By + Cz = P 

위의 디오판토스 방정식의 음이 아닌 정수 해 (x, y, z) 의 개수를 구하는 문제이다.

우선 위에서 주어진 두 조건 중 두번째 조건을 주목하자. C / gcd(A, B, C) 가 200이상이라는 말은 일단

적어도 입력으로 들어오는 C가 200이상이라는 것을 알 수 있다. 그러면 z를 고정시키고 그에 대한 (x, y) 를 구하는

식으로 계산한다치면, 최악의 경우에도 고정하는 z의 개수는 10^8 / 200 이하, 즉 50만개 이하가 된다.

그럼 z를 고정시키고 x, y 를 구해보자. 만약 z가 정해지면 오른쪽 항으로 넘겨서

Ax + By = P'

의 형태를 만들 수가 있다.

그럼 확장 유클리드로 특수해를 하나 구한 뒤, 전체 해의 양쪽 경계를 O(1) 에 계산하여

전체 개수를 구하는 식으로 답에 누적해나가면 된다.

시간복잡도는 O((L/C)lgL) ( 0 < L < 10^8, 200 <= C < L)

#include <bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
ll trash;
 
ll xGCD(ll a, ll b, ll& x, ll& y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    ll x1, y1;
    ll ret = xGCD(b, a % b, x1, y1);
    x = y1, y = x1 - (a / b) * y1;
    return ret;
}
 
ll findRng(ll x0, ll y0, ll a, ll b){
    if(y0 <= 0) {
        swap(x0, y0);
        swap(a, b);
    }
    ll g = xGCD(a, b, trash, trash);
    ll dx = b / g, dy = - a / g;
    ll t1, t2;
    if(x0 < 0) t1 = (-x0 + dx - 1) / dx;
    else t1 = 0;
    t2 = y0 / (-dy);
    return max(0ll, t2 - t1 + 1);
}
 
ll T, A, B, C, P;
ll a, b, p;
int main() {
    fastio();
    cin >> T;
    for(ll t = 1; t <= T; t++){
        cout << "Case " << t << ": ";
        cin >> A >> B >> C >> P;
        ll ans = 0;
        for(int i = 0 ; i * C < P; i++){
            ll p = P - i * C;
            ll g = xGCD(xGCD(A, B, trash, trash), p, trash, trash);
            a = A / g, b = B / g, p /= g;
            ll x, y;
            ll gg = xGCD(a, b, x, y);
            if(gg != 1) continue;
            ans += findRng(x * p, y * p, a, b);
        }
        if(P % C == 0) ans++;
        cout << ans << endl;
    }
    return 0;
}