POJ 1061 青蛙的约会（欧几里得扩展）

　　题意：已知青蛙1位置x，速度m，青蛙2位置y，速度n，纬线长度为l，求他们相遇时最少跳跃次数。

　　思路：设最小跳跃次数为k，则（x + k*m） - （y + k*n） = q*l；经过整理得到k*（n-m） + q*l = x - y；此时k和l为变量。欧几里得扩展中有线性方程a*x+b*y = c，当且仅当c是gdc（a，b）的整数倍的时候，所以这个题我们可以使用这个算法求得一个x0（x0已经被乘以了倍数），故x0为满足题意的一个解，X的解系为x0 + k【b/gcd(a，b)】（具体证明不在给出，刘汝佳算法竞赛入门数论基础中有很好的证明），但是题目中要求我们要求得最小的正整数X，用到下面的定理：

若gcd(a, b) = d，则方程ax ≡ c (mod b)在[0, b/d - 1]上有唯一解，也就是X在这个区间内有唯一解，而且这个解就是我们想要的最优解，我们假设b/d = c，那通过

(X%r + r) % r的操作我们可以把x转化到（0，r-1）这个区间内，这就是我们要找的最优解。代码如下：

　　注意：其实gcd = 0的时候是需要特殊判断的，但是这个题的数据没有难为我们，我也是AC后想起来的。还有这个题数据比较大，要用long long。最后希望读者知道，等式两边正负号并不影响我们的判断。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define LL long long

LL x,y;

LL ex_gcd(LL a,LL b)

{

    if(b == ){

        x = ;

        y = ;

        return a;

    }

    LL gcd = ex_gcd(b,a%b);///x与y求解的方法并不难，两个式子相等就可以解出来

    LL tmp = x;

    x = y;

    y = tmp - (a/b)*y;

    return gcd;

}

int main()

{

    LL x1,y1,m,n,l;

    while(~scanf("%I64d %I64d %I64d %I64d %I64d",&x1,&y1,&m,&n,&l)){

        LL a = (n-m);

        LL b = l;

        LL c = (x1-y1);

        LL gcd = ex_gcd(a,b);

        if(c % gcd != ){

            puts("Impossible");

            continue;

        }

        LL k = c / gcd;

        LL tmp = b / gcd;

        x = x * k;///我们需要把它扩大k倍，因为x是我们求出的最大公约数的情况。

        x = (x%tmp + tmp) % tmp;///如上述操作

        printf("%I64d\n",x);

    }

    return ;

}

巴特西

POJ 1061 青蛙的约会（欧几里得扩展）

最新文章

热门文章