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

本文主要是介绍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) );elseup = min(up, (ll)floor( (-1.0*x*C) / B) );if (A / d > 0)up = min(up, (ll)floor( (1.0*y*C) / A));elselower = 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");elseprintf("%lld\n", up - lower + 1);
}int main () {int cas;scanf("%d", &cas);while (cas--) {scanf("%lld%lld%lld", &A, &B, &C);solve();}return 0;
}

这篇关于uva 10548 - Find the Right Changes(拓展欧几里得)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---