nefu 84 http://acm.nefu.edu.cn/test/problemshow.php?problem_id=84

#include<iostream>
using namespace std;

typedef long long inta;
int extend_gcd(inta a,inta b,inta &x,inta &y,inta &gcd)

{
   if(b==0)
   {
      x=1;
      y=0;
      gcd=a;
   }

   else
   {
      extend_gcd(b,a%b,x,y,gcd);
      int temp=x;
      x=y;
      y=temp-a/b*y;
   }
}

int gcd(int a,int b)
{
   if(b==0)
   return  a;

   else return gcd(b,a%b);

}
int main()

{
   inta n,d,x,y;
   int times;
   cin>>times;
   while(cin>>n>>d>>x>>y)
   {
      inta a=d;
      inta b=n;
      inta c=y-x;
      inta s=gcd(a,b);
       if(c%s!=0)
      {
         cout<<"Impossible"<<endl;
      }

       else
      {
        inta x0,y0,q;
        a/=s;
        b/=s;
        c/=s;
        extend_gcd(a,b,x0,y0,q);
        x0*=c;
        if(b<0)  b=-b;

        x0=(x0%b+b)%b;
        cout<<x0<<endl;
      }
   }
}

//  和青蛙的约会一样