EXGCDWA的问题很大求助
查看原帖
EXGCDWA的问题很大求助
333800
qip101楼主2022/7/6 15:55
#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
long long x0,y0,k;
long long T;
long long gcd(long long a,long long b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	long long d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
int main()
{
	ios::sync_with_stdio(false);
	cin >> T;
	while(T--)
	{
		long long a,b,c;
		cin >> a >> b >> c;
		long long d=exgcd(a,b,x0,y0);
		long long x1=x0*c/d,y1=y0*c/d;
		long long dx=b/d,dy=a/d;
		if(c%gcd(a,b)!=0)
		{
			cout << "-1" << endl;
			continue;
		}
		else
		{
			if((1-x1)/dx > (y1-1)/dy)
			{
				long long x_min=x1+(1-x1)/dx*dx;
				long long y_min=y1-(y1-1)/dy*dy;
				cout << x_min << " " << y_min << endl;
			}
			else
			{
				long long tot=((y1-1)/dy) - ((1-x1)/dx);
				long long x_min=x1+(1-x1)/dx*dx;
				long long y_min=y1-(y1-1)/dy*dy;
				long long x_max=x1+(y1-1)/dy*dx;
				long long y_max=y1-(1-x1)/dx*dy;
				cout << tot << " " << x_min << " " << y_min << " " << x_max << " " << y_max << endl;
			}	
		}
	}
	return 0;
}
2022/7/6 15:55
加载中...