青蛙的约会+拓展欧几里得+题解

纵有疾风起

题意

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

输入

输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

输出

输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"

前话-拓展欧几里得（下方高能！！！）

扩展欧几里德算法是用来在已知a, b求解一组整数解x，y，使它们满足贝祖等式（具体不是很清楚是啥意思，反正就那样）： \(ax+by = gcd(a, b) =d\)（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。

对于普通的公式\(ax+by = c\)有整数解的条件是\(c=k*gcd(a, b)\)，k为任意常数。

对于公式\(ax+by = gcd(a, b) =d\)，求解其中一个x，y的方法及其证明

显然当 \(b=0,gcd(a,b)=a\)时，此时 \(x=1, y=0\)；

\(a>b>0\) 时，设 \(ax_1+ by_1= gcd(a,b)\);

\(bx_2+ (a\ mod\ b)*y_2= gcd(b,\ a\ mod\ b)\);

根据朴素的欧几里德原理有 \(gcd(a,b) = gcd(b,a\ mod\ b)\);

则:\(ax_1+ by_1= bx_2+ (a\ mod\ b)y_2\);

即:\(ax_1+ by_1= bx_2+ (a - [a / b] * b)y_2=ay_2+ bx_2- [a / b] * by_2\)。

说明： \(a-[a/b]b\)即为mod运算。\([a/b]\)代表取小于\(a/b\)的最大整数，下面同样适用。

也就是\(ax_1+ by_1 == ay_2+ b(x_2- [a / b] *y_2)\);

根据恒等定理，对应项的系数相等得：

\(x_1=y_2\); \(y_1=x_2- [a / b] *y_2\);

这样我们就得到了求解 \(x_1,y_1\) 的方法：\(，x_1，y_1\) 的值基于\(， x_2，y_2\)。使用递归的话，上一层的值，取决于下一层。

上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

递归边界：\(（）gcd（a,\ 0）=1*a-0*0=a\)。

对于公式\(ax+by = c\)，求解x，和y的方法

如果\(c\ \%\ gcd( a , b) != 0\)，即c不是gcd的整数倍，则无解。

如果\(c\ \%\ gcd(a,b) == 0\) ，则\(c\ /\ gcd(a,b) = t\)，那么求出方程 \(a * x + b * y = gcd(a,b)\)的所有解x,y，将x,y乘上t，对应的x’,y’即是方程\(a * x + b * y = t * gcd(a,b)\)的一个解

如何求\(ax+by = gcd(a, b) =d\)最小整数解，对于\(ax+by = c\)，c为常数，也适用。

我们可以用扩展欧几里得算法得出

\[ax+by=gcd(a,b)
\]

的一组解\(（x_1,\ y_1）\)，那么其他解呢？任取另一组解\(（x_2,\ y_2）\),则

\[ax_1+by_1=ax_2+by_2
\]

（因为它们都等于\(gcd(a,b)\) ），变形得

\[a(x_1-x_2)=b(y_2-y_1)
\]

假设\(gcd(a,\ b)=g\)，方程左右两边同时除以g（如果g=0，说明a或b等于0，可以特殊判断），得

\[a'(x_1-x_2)=b'(y_2-y_1)
\]

其中\(，a'=a/g，b'=b/g\)。

注意，此时a'和b'互素（想想分数的化简）

\[x_1-x_2=\frac{b'}{a'}*(y_2-y_1)
\]

则因此\(x_1-x_2\)一定是b'的整数倍（因为a'中不包含b'，所以\(x_1-x_2\)一定包含b'）。

设它为\(x_1-x_2=k*b'\)，计算得\(y_2-y_1=k*a'\)。注意，上述的推导过程并没有用到\(ax+by\)的右边是什么，因此得出以下结论：

设a,b,c为任意整数，若方程\(ax+by=c\)的一组解是\((x_0,y_0)\)，则它的任意整数解都可以写

\((x_0+k*b',y_0-k*a')\)，其中\(a'=[a/gcd(a,b)]\)，\(b'=[b/gcd(a,b)]\)，k取任意整数。

这样我们就可以求出来最小的整数解了。（先用扩展欧几里得算法求出一组解，然后进行变换）

解题思路

根据题意，两只青蛙需要在同一时间到达用一个点上才算相遇，易得(设t就是所求的答案)

\[(m*t+x)\%L=(n*t+y)\%L
\]

因为\((m*t+x)=w*L+v\)，\((n*t+y)=s*L+v\)

两边相减得

\[(n-m)*t+(w-s)*L=x-y
\]

令\(a=n-m\)，\(b=L\)，\(c=x-y\)， \(X=t\)， \(Y=w-s\)

然后就是拓展欧几里得的处理了

代码

#include <cstdio>

#include <cstring>

#include<cmath>

#include <algorithm>

using namespace std;

typedef long long ll;

void extended_gcd(ll a,ll b,ll &x,ll &y) //注意参数，后两个是c++里面的引用

{

    ll r,t;

    if(b==0)

    {

        x=1;

        y=0;

        return ;

    }

    extended_gcd(b,a%b,x,y);

    t=x;

    x=y;

    y=t-a/b*y;

}

int main()

{

    ll x,y,m,n,L,g,c,a,b;

	scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L);

    a=n-m;

    c=x-y;

    b=L;

    g=__gcd(a, b);

    if(c%g!=0)

        printf("Impossible\n");

    else

    {

    	extended_gcd(a,b,x,y);

        x=x*c/g;

        ll t=b/g;

        if(x>=0) //如果最初求的解大于零，后面就直接模b/g就行

            x=x%t;

        else

            x=x%t+t;//如果小于零，就先模，然后加上b/g后就一定大于0了

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

    }

    return 0;

}

巴特西

poj 1061 青蛙的约会+拓展欧几里得+题解

青蛙的约会+拓展欧几里得+题解

题意

前话-拓展欧几里得（下方高能！！！）

解题思路

代码

END

最新文章

热门文章