学步园

题意：两只青蛙在同一条纬度线上，它们约定各自朝西跳，直到碰面为止。规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。（x≠y
< 2000000000，0 < m、n < 2000000000，0 < L < 2100000000）

题目链接：http://poj.org/problem?id=1061

——>>过年的第一道题目啊，哈哈～～0MS过！假设前面的青蛙跳得比较快，第一次追上后面的青蛙时，快的青蛙比慢的青蛙多跳了一圏，但追上不一定落在同一点上，如果没有落在同一点上，那么继续跳，下次追上时快的比慢的已多跳了两圈……所以，如果两只青蛙能够相遇，那么它们的差距必为L的整数倍，即满足(x + m * X) - （y + n * X） = Y * L；整理，得(n-m) * X + L * Y = x - y；这是两元一次方程，正好可用扩展的欧几里德定理。求得其中的一组解，设为(x0, y0)， 那么原方程的通解为：x
= x0 + b * t, y = y0 - a * t（t为参数）；于是可用t = -x0 / b求得一个边界，如果此时x大于等于0，直接输出，如果此时x小于0，那么加上一个b再输出即可。

#include <cstdio>

using namespace std;

long long gcd(long long a, long long b)
{
    return b == 0 ? a : gcd(b, a%b);
}
void Euler_extends(long long a, long long b, long long d, long long &x, long long &y)
{
    if(!b)
    {
        x = 1;
        y = 0;
    }
    else
    {
        Euler_extends(b, a%b, d, y, x);
        y -= a / b * x;
    }
}
int main()
{
    long long x, y, m, n, L, X, Y;
    while(~scanf("%I64d%I64d%I64d%I64d%I64d", &x, &y, &m, &n, &L))
    {
        long long a = n - m, d = x - y, g = gcd(n-m, L);
        if(d % g != 0)
        {
            printf("Impossible\n");
            continue;
        }
        g = gcd(a, L);
        a /= g;
        L /= g;
        d /= g;
        Euler_extends(a, L, d, X, Y);
        X *= d;
        Y *= d;
        long long t = -X / L;       //求临界
        X = X + L*t;
        if(X < 0) X += L;
        printf("%I64d\n", X);
    }
    return 0;
}