本文主要是介绍SGU 106 The equation(拓展欧几里得)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
通解形式
然后利用x，y去求出范围，就能得到解的个数
注意特判a和b都为0的情况
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;typedef long long ll;
ll a, b, c;
double a1, a2, b1, b2;ll exgcd(ll a, ll b, ll &x, ll &y) {if (!b) {x = 1; y = 0; return a;}ll d = exgcd(b, a % b, y, x);y -= x * (a / b);return d;
}ll solve() {ll x, y;if (a == 0 && b == 0) {if (c == 0) return (a2 - a1 + 1) * (b2 - b1 + 1);return 0;}ll d = exgcd(a, b, x, y);if (d < 0) d = -d;if (c % d) return 0;double l = -1e50, r = 1e50;if (b / d < 0) {r = min(r, floor((a1 - c / d * 1.0 * x) / (b / d)));l = max(l, ceil((a2 - c / d * 1.0 * x) / (b / d)));} else {l = max(l, ceil((a1 - c / d * 1.0 * x) / (b / d)));r = min(r, floor((a2 - c / d * 1.0 * x) / (b / d)));}if (a / d < 0) {l = max(l, ceil((c / d * 1.0 * y - b1) / (a / d)));r = min(r, floor((c / d * 1.0 * y - b2) / (a / d)));} else {r = min(r, floor((c / d * 1.0 * y - b1) / (a / d)));l = max(l, ceil((c / d * 1.0 * y - b2) / (a / d)));}return max(0LL, (ll)(r - l) + 1);
}int main() {while (~scanf("%lld%lld%lld", &a, &b, &c)) {c = -c;scanf("%lf%lf", &a1, &a2);scanf("%lf%lf", &b1, &b2);printf("%lld\n", solve());}return 0;
}
这篇关于SGU 106 The equation(拓展欧几里得)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
