poj 1061 青蛙的约会 二元一次不定方程 http://poj.org/problem?id=1061

#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 x,y,m,n,l;
   while(cin>>x>>y>>m>>n>>l)
   {
      inta a=n-m;
      inta b=l;
      inta c=x-y;
      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;
      }
   }
}

//  1 扩展欧几里得算法，利用递归求出 Bezout等式中x和y的值

//  2  不知道a的正负性时a mod b=(a%b+b0%b

//  3 ax+by=c; gcd(a,b)=1;  x的通解模b同余，要求取最下的非负整数就在完系中取即可