POJ1061 青蛙的约会(扩展欧几里德)

题目链接

中文题。

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

思路:设跳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;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 数学