POJ1061 青蛙的约会（扩展欧几里德）

February 14, 2016

题目链接

关于扩展欧几里德算法的讲解，推荐这篇文章。

思路：设跳 t 次，则 x+mt 是青蛙 A 从坐标原点到终点所走的距离，y+nt 是 B 走的距离，要想碰面，则他们相减一定是地面周长的整数倍，则：(x+mt)-(y+nt)=kl; 变形得：(m-n)t-(y-x)=kL; 即(n-m)t+Lk = x-y. 设 a=n-m, b=L, d = x-y.则可以写成 at+bk=d.这时问题转化成了：求最小正整数 t 满足上式。

根据扩展欧几里德算法可以求出 a*t0+b*k0=gcd(a,b)中 t0，k0 的一组解和 gcd，将 t0,k0,gcd 三个数除以 gcd 乘以 d 后这个式子就变成了原式。所以 t = t0*d/gcd. 但这只是一组解，如何让 t 最小？

观察 at+bk=d 这个式子，可以写成 a(t+bn)+b(k-an) = d. （n 为自然数）。也就是说通解写成了 t+bn，那么对计算出的 t 进行如下运算可以得出最小的 t： t = (t%b+b)%b .

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
//返回d=gcd(a,b);x和y对应于等式ax+by=d中的x,y
long long ex_gcd(long long a,long long b,long long &x,long long &y){
    if(a==0 && b==0) return -1;//无最大公约数
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    long long d = ex_gcd(b, a%b, y, x);
    y -= a/b*x;
    return d;
}
int main(){
    //freopen("a.txt", "r", stdin);
    long long x, y, m, n, l, d, xx, yy;
    while(~scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &l)){
        d = ex_gcd(n-m, l, xx, yy);
        if((x-y)%d != 0) printf("Impossiblen");
        else{
            xx = xx*(x-y)/d;
            xx = (xx%l+l)%l;
            cout << xx << endl;
        }
    }
    return 0;
}