其实同POJ 1061

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;long long  gcd(long long a,long long b){	if(b==0) return a;	return gcd(b,a%b);}void exgcd(long long a,long long b,long long &x,long long &y){	if(b==0){		x=1; y=0; return;	}	exgcd(b,a%b,x,y);	long long t=x;	x=y;	y=t-a/b*y;}int main(){	int t;	long long n,d,x,y,a,b,c;	scanf("%d",&t);	while(t--){		cin>>n>>d>>x>>y;		a=n; b=d; c=y-x;		long long r=gcd(a,b);		if(c%r!=0){			printf("Impossible\n");			continue;		}		a/=r; b/=r; c/=r;		exgcd(a,b,x,y);		y*=c;		printf("%lld\n",(y%a+a)%a);	}	return 0;}