POJ 1061 青蛙的約會

先說一下大概題意：有兩只青蛙，一只在坐標x，另一直在坐標y，青蛙x一次跳躍可以前進m單位距離，青蛙y一次跳躍可以前進n單位的距離，兩青蛙都在同一緯度，該緯度長度為L。兩只青蛙同方向同時跳啊跳，問你最少跳多少次，它們才可以相遇，如果不能相遇，輸出impossble

分析：假設跳了T次以後，青蛙1的坐標便是x+m*T,青蛙2的坐標為y+n*T。它們能夠相遇的情況為（x+m*T）-(y+n*T)==P*L，其中P為某一個整數，變形一下
得到(n-m)*T+P*L==x-y   我們設a=(n-m),b=L,c=x-y,T=x,P=y.於是便得到ax+by==c。激動啊，這不就是上面一樣的式子嗎~
直接套用擴展歐幾裡得函數，得到一組解x,y。由於問題是問最少跳多少次，於是只有x是我們需要的信息。那麼再想，x是最小的嗎？

答案是可能不是！那麼如何得到最小解呢？  我們考慮x的所有解的式子： x=x0+b/d*t。x0是我們剛剛求到的，很顯然右邊是有個單調函數，當t為某一個與x正負性質相反的數時，可以得到最小的x。 令x的正負性質為正，那麼x=x0-b/d*t1 (t1==-t)。令x==0，那麼t=x0*d/b，最小的x等於x0減去t*b/d。這裡得到的x可能是負數，如果是負數，我們再為它加上一個b/d即是所求答案了！

AC代碼：

#include<iostream>   
#include<string>   
#include<cmath>   
#include<algorithm>   
usingnamespace std;  
  
__int64 x,y,a,b,c,d;  
__int64 n,m,X,Y,L;  
  
__int64 gcd(__int64 a,__int64 b)  
{  
    __int64 t,d;  
    if(b==0)  
    {  
        x=1;  
        y=0;  
        return a;  
    }  
    d=gcd(b,a%b);  
    t=x;  
    x=y;  
    y=t-(a/b)*y;  
    return d;  
}  
  
int main()  
{  
    while(scanf("%I64d%I64d%I64d%I64d%I64d",&X,&Y,&m,&n,&L)==5)  
    {  
        a=n-m;  
        b=L;  
        c=X-Y;  
        d=gcd(a,b);  
        if(c%d!=0)  
        {  
            printf("Impossible\n");  
            continue;  
        }  
        x=x*(c/d);  
        y=y*(c/d);  
  
        /*通解： 
        x1=x+b/d*t; 
        y1=y-a/d*t; 
        t為任意整數 
        */  
        //找最小的x1，即求x+b/d*t最小，那麼只有t為某一個數時才最小   
        //顯然t必須與x正負相反才有最小，那麼就看做x-b/d*t,這個式子的最小值便是t=x/(b/d)時，注意這是整型除法   
        __int64 k=x*d/b;  
        k=x-k*b/d;  
        if(k<0)  
            k+=b/d;  
        printf("%I64d\n",k);  
    }  
    return0;  
}