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;
}

Profile picture

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]