0pts求助,已知exgcd没问题
查看原帖
0pts求助,已知exgcd没问题
800499
suzhikz楼主2024/9/27 13:24
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
#define int long long 
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
//void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
int gcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;y=0;
		return a;
	}
	int g=gcd(b,a%b,x,y);
	int z=x;
	x=y;
	y=z-(a/b)*y;
	return g;
}
int t,a,b,c,g;
signed main(){
	read(t);
	while(t--){
		read(a);read(b);read(c);
		int x,y;
		g=gcd(a,b,x,y);
		if(c%g!=0){
			puts("-1");
		}else{
			x*=c/g,y*=c/g;
//			cout<<x<<' '<<y<<' '<<g<<endl;
			int dx=b/g,dy=a/g;
//			cout<<dx<<' '<<dy<<endl; 
			int r=y/dy,l=-x/dx;
//			cout<<r<<endl;
//			cout<<r<<endl;
			if(r==y*dy)r--;
//			cout<<r<<' '<<dy<<' '<<r*dy<<endl<<y<<endl;
			l++;
//			cout<<r<<endl;
//			r--;
//			cout<<l<<' '<<r<<endl; 
			if(r-l>=0){
				cout<<r-l+1<<' ';
				cout<<x+l*dx<<' '<<y-r*dy<<' ';
				cout<<x+r*dx<<' '<<y-l*dy<<endl;
			}else{
				int a=(x%dx+dx)%dx,b=(y%dy+dy)%dy;
				if(a==0)a=dx;if(b==0)b=dy;
				cout<<a<<' '<<b<<endl;
			}
		}
	}
	return 0;
}

2024/9/27 13:24
加载中...