uva 10548 – Find the Right Changes(拓展欧几里得)

题目链接：uva 10548 – Find the Right Changes

题目大意：给定A，B，C，求x，y，使得xA+yB=C，求有多少种解。

解题思路：拓展欧几里得，保证x，y均大于等于0，确定通解中t的取值。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f;

ll A, B, C;

void gcd (ll a, ll b, ll& d, ll& x, ll& y) {
    if (b == 0) {
        d = a;
        x = 1;
        y = 0;
    } else {
        gcd(b, a%b, d, y, x);
        y -= (a/b) * x;
    }
}

void solve () {
    ll d, x, y;
    gcd(A, B, d, x, y);

    if (C % d) {
        printf("Impossible\n");
        return;
    }

    ll up = INF, lower = -INF;

    if (B / d > 0)
        lower = max(lower, (ll)ceil( (-1.0*x*C) / B) );
    else
        up = min(up, (ll)floor( (-1.0*x*C) / B) );

    if (A / d > 0)
        up = min(up, (ll)floor( (1.0*y*C) / A));
    else
        lower = max(lower, (ll)ceil( (1.0*y*C) / A));

    if (up == INF || lower == -INF)
        printf("Infinitely many solutions\n");
    else if (up < lower)
        printf("Impossible\n");
    else
        printf("%lld\n", up - lower + 1);
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%lld%lld%lld", &A, &B, &C);
        solve();
    }
    return 0;
}