全WA求调
查看原帖
全WA求调
1161241
FuHua19451001楼主2024/9/6 12:31
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll read() {
	char c = getchar();
	int f = 1;
	ll x = 0;
	while (c < '0' || c>'9') {
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 1) + (x << 3) + (c ^ '0');
		c = getchar();
	}
	return x * f;
}

ll x, y;
ll exgcd(ll a, ll b) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	else {
		ll d = exgcd(b, a % b);
		ll tmp = x;
		x = y;
		y = tmp - a / b * y;
		return d;
	}
}

ll a, b, c;
void sol() {
	ll a = read();
	ll b = read();
	ll c = read();

	ll d = exgcd(a, b);
	if (c % d!=0) {
		cout << -1 << endl;
		return;
	}

	//计算原方程特解
	ll x1 = x * c / d;
	ll y1 = y * c / d;
	//cout<<"x:"<<x1<<" "<<"y:"<<y1<<endl;

	ll dx = b / d;
	ll dy = a / d;
	//cout << "dx:" << dx << " " << "dy:" << dy << endl;
	//判断有无正整数解
	ll down = ceil((-x1 + 1) / dx);
	ll up = floor((y1 - 1) / dy);

	//cout << "down:" << down << " " <<"up:"<< up << endl;

	if (down > up) {
		ll x_min = x1 + down * dx;
		ll y_min = y1 - up * dy;
		cout << x_min << " " << y_min << endl;
		return;
	}
	else {
		ll x_min = x1 + down * dx;
		ll y_max = y1 - down * dx;
		ll x_max= x1 + up * dx;
		ll y_min= y1 - up * dx;

		cout << up - down << " " << x_min << " " << y_min << " " << x_max << " " << y_max << endl;
		return;
	}
	
}

ll n;
int main() {
	cin >> n;
	while (n--) {
		sol();
	}
}
2024/9/6 12:31
加载中...