通过POJ1061青蛙的约会来谈扩展欧几里得算法

9月 16

对于题目中的数据，详见下表

故，可得两只青蛙跳四次就可以在点3处相遇

对于这道题可以知道，当他们相遇时距离原点的位移是相等的，则假设青蛙跳了t次后，则他们相对于原点的位移是

A：$(x+mt）\bmod l$

B：$(y+nt）\bmod l$

则可以列方程$(x+mt) -(y+nt)=cl (c为整数)$

则变形得$(m-n)t-cl=y-x$;

题目要求的就是要使等式成立时最小时的正整数t

在解决这个问题前，我们首先就应该知道什么是扩展欧几里得算法

即找出一对整数$(x，y)$，使得$ax+by=gcd(a，b)$。

注意，这里的$x$和$y$不一定是正数，也可能是负数或者$0$.

下面是扩展欧几里得算法的源程序：（参考刘汝佳的《算法竞赛入门经典》第179页）

void gcd ( int a , int b , int& d , int& x , int& y )
{//a，b分别代表方程的系数，d返回a，b的最大公约数，x，y返回对应的解
    if ( ! b )//当b等于0的时候，方程就变成了ax=gcd（a，0）=a，所以此时明显可以得到方程的解为x=1，y=0，此时d就为a
        d = a , x =1 , y =0 ;
     else
     {//递归求方程的解，等下证明
          gcd ( b , a % b , d , y , x ) ;
          y -= ( a / b ) * x ; 
    }
}

书上对该算法没有给出证明，只有“用数学归纳法并不难证明算法的正确性”一笔代过，现在，去我们就来证明该算法的正确性

当$b=0$时很好理解，详见上面的注释

关键是当$ b \neq 0 $，则我们先来假设方程的$ax+by=gcd(a，b)=d$的一个正整数解为$x_1$，$y_1$；别怀疑，这个方程一定有解

则有①：$ax_1+by_1=gcd(a，b)$

又对于方程$bx +(a \bmod b)y = gcd (b ,a \bmod b )$ 有解$x_2$，$y_2$（假设）

则有②：$bx_2+(a \bmod b)y_2 = gcd (b ,a \bmod b) = gcd(a, b)$

又$a \bmod b = a - (a/b)b$；

则②式变为$bx_2+(a-(a/b)b)y_2=gcd(a,b)$;

即③：$ay_2 + b(x_2-(a/b)*y_2) = gcd (a,b)$;

对比①③得

$x_1=y_2$

$y_1 = x_2 - (a/b)y_2$

故，$ax+by=gcd(a，b)$的解只需要在方程$bx +(a \bmod b)y =gcd (b ,a \bmod b )$的解的基础上进行简单的运算就变成原来方程的解，因为gcd不断递推时会有$b=0$的情况出现，故可以通过递推来得到方程的解

然后得出了关于方程$ax+by=gcd(a，b)$的解$x_0$，$y_0$，

但如何要求题目所要求的解了；

假设方程是$ax+by=c$；

现在我们已经知道了$ax+by=gcd(a，b)$的解$x_0$，$y_0$，即$ax_0+by_0=gcd(a，b)$；

则等式两边同乘以$c/gcd(a，b)$则得

$ax_0c/gcd(a,b)+by_0c/gcd(a,b)=c$;(则可知人如果c不是$gcd(a，b)$的倍数则无解)

故可以得到原方程的一个解是$x_1=x_0c/gcd(a,b)$，$y_1=y_0c/gcd(a,b)$

再根据下面的结论就可以很好的得出此题的答案了

设$a，b，c$为任意整数。若方程$ax+by=c$的一组整数解为$(x_0，y_0)$，则它的任意整数解都可以写成$(x_0+kb’,y_0-ka’)$,其中$a’=a/gcd(a，b)$，$b’=b/gcd(a，b)$，$k$为任意整数

关于上面的结论很好证明，此处略。

刚开始的时候没有注意到怎样就解答系，WA了两次

poj1061 青蛙的约会view raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

void gcd ( __int64 a , __int64 b , __int64 &d , __int64 &x , __int64 &y )
{

    if ( ! b ) 
        d = a , x = 1 , y = 0 ;
    else 
        gcd ( b , a%b , d , y , x ) , y -= x * ( a / b ) ; 
}

int main()
{
    __int64 s , t , m , n , l ;
    while ( ~ scanf ("%I64d%I64d%I64d%I64d%I64d" , & s , & t , & m , & n , & l ) )
    {
        __int64 a , b , d , ans ;
        __int64 x , y ;
        a = l ;
        b = m - n ;
        ans = t - s ;
        if ( b < 0 )
            b = n - m , ans = s - t ;
        gcd ( a , b , d , x , y ) ;
        if ( ans % d )//无解出现的情况
            printf("Impossible\n") ;
        else
        {
            __int64 tmp = l / d ;        
            ans = (  ans / d * y ) % tmp ;//求出答案，因答案要求最小，故还得对答案的“周期”取余
            if ( ans < 0 )//如果出现的是负数，就要加上周期
                ans += tmp ;
            printf ("%I64d\n",ans);
        }
    }
    return 0;
}