POJ 1061 青蛙的约会 (扩展欧几里得)

Description

Input

Output

Sample Input

1 2 3 4 5

Sample Output

4

题意，求解最少的时间，让得两个青蛙可以相遇。
这道题目涉及的扩展欧几里得知识，请读者自行补脑，这里只说明为什么可以用扩展欧几里得以及怎么用扩展欧几里得去算出结果
有题目可以列出方程式：
(x + m * t) % L - (y + n * t) % L == 0
如此可以写成 x - y + (m - n) * t == p * L,如果青蛙A与青蛙B在相同时间内行驶的距离的差为L的倍数，那么他们能够相遇
接着运用扩展欧几里得求解他们一个整数解
a = (m - n)
b = L
void gcd(LL a,LL b,LL &d, LL &x, LL &y){
    if(!b){
        d = a;
        x = 1;
        y = 0;
    }
    else{
        gcd(b,a % b, d, y, x);
        y -= x * (a / b);
    }
}
其中d为最大公约数
于是如果(x - y) 不是最大公约数的倍数，证明没有整数解（理由，请自行看扩展欧几里得的知识点）
接着是求解最小的t,很明显
有扩展欧几里得可以知道
此时求解的X,Y并非整数解而是方程
{x - y + (m - n) * t == p * L} -> {(n - m) * t + p * L == x - y} -> {(n - m) * t + p * L == gcd(n - m, p)的解}
所以我们还要将它转换为整数解进行求值（此处的求解属于扩展欧几里得范畴）
t =X * (x - y) / d即为答案，但是这里要注意就是会出现负数的情况
所以t = ((t + L) % L + L) % L

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


void gcd(LL a,LL b,LL &d, LL &x, LL &y){
    if(!b){
        d = a;
        x = 1;
        y = 0;
    }
    else{
        gcd(b,a % b, d, y, x);
        y -= x * (a / b);
    }
}
int x, y, m, n, L;
int main(){
    while(~ scanf("%I64d%I64d%I64d%I64d%I64d",&x, &y, &m, &n, &L)){
        LL d,X,Y;
        gcd(m - n, L, d, X, Y);
        if((y - x) % d!= 0){
            printf("Impossible\n");
        }
        else{
            X *= (x - y) / d;
            X =((L - X) % L + L) % L;
            printf("%I64d\n",X);
        }
    }
    return 0;
}

POJ 1061 青蛙的约会 (扩展欧几里得)

原文：http://blog.csdn.net/qq_18661257/article/details/47663137