青蛙的約會 POJ - 1061

​​http://poj.org/problem?id=1061​​

兩隻青蛙是同時跳的 如果兩隻青蛙的步子一樣大 那永遠也無法相遇

否則 考慮用拓展歐幾裡得求(a*x)%b=c的最小非負整數解 将步子之差(m-n)作為a 總長度l作為b 初始距離y-x作為c（注意不能是(x-y)）即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

void exgcd(ll a,ll b,ll& x,ll& y)
{
    ll tx,ty;
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,tx,ty);
    x=ty,y=tx-a/b*ty;
}

int main()
{
    ll xx,yy,m,n,l;
    ll a,b,c,gcd,x,y,s;
    scanf("%lld%lld%lld%lld%lld",&xx,&yy,&m,&n,&l);
    if(m==n) printf("Impossible\n");
    else{
        a=n-m,b=l,c=xx-yy;
        exgcd(a,b,x,y);
        gcd=a*x+b*y;
        if(c%gcd!=0) printf("Impossible\n");
        else{
            x*=(c/gcd);
            s=abs(b/gcd);
            x=(x%s+s)%s;
            printf("%lld\n",x);
        }
    }
    return 0;
}