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 易做图(__int64 a,__int64 b)  
{  
    __int64 t,d;  
    if(b==0)  
    {  
        x=1;  
        y=0;  
        return a;  
    }  
    d=易做图(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=易做图(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;  
}

补充：软件开发 , C++ ,