首页 > 代码库 > POJ-1061 青蛙的约会-数论扩展欧几里德算法入门及推导

POJ-1061 青蛙的约会-数论扩展欧几里德算法入门及推导

Description

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

Input

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

Output

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

Sample Input

1 2 3 4 5

Sample Output

4
#include<stdio.h>
#include<iostream>
using namespace std;
__int64 t,p;
__int64 gcd(__int64 a,__int64 b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
void extend_gcd(__int64 a,__int64 b)
{
    if(b==0)
    {
        t=1;
        p=0;
    }
    else
    {
        extend_gcd(b,a%b);
         __int64 temp=t;
        t=p;
        p=temp-a/b*p;
    }

}
int main()
{
    __int64 x,y,n,m,l;
    __int64 a,b,c,a1,b1,c1,count;
   scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);

        a=n-m;
        b=l;
        c=x-y;
       if(c%gcd(a,b)!=0||m==n)
        {
            printf("Impossible\n");
           return 0;
        }

            count=gcd(a,b);
            a=a/count;
            b=b/count;
            c=c/count;
            extend_gcd(a,b);
        t*=c;
        p*=c;
        t=(t%b+b)%b;
            printf("%lld\n",t);







    return 0;
}

扩展欧几里德算法-求解不定方程,线性同余方程:
解不定方程ax  +  by  =  n的步骤如下: 
 
(1)计算gcd(a,  b).  若gcd(a, b)不能整除n,则方程无整数解;否则,在方程的两边同除以gcd(a, b),
   得到新的不定方程a‘x  +  b‘y =  n‘,此时gcd(a‘,  b‘)  =  1 
 
(2)求出不定方程a‘x  +  b‘y  =  1的一组整数解x0,  y0,则n‘x0,n‘y0是方程a‘x  +  b‘y  =  n‘的一组整数解。 
 
(3)根据&@^%W#&定理,可得方程a‘x +  b‘y  =  n‘的所有整数解为: 
    x  =  n‘x0  +  b‘t 
    y  =  n‘y0  -  a‘t 
   (t为整数) 
这也就是方程ax  +  by  =  n的所有整数解 
 
利用扩展的欧几里德算法,计算gcd(a,  b)和满足d  =  gcd(a,  b)  =  ax0  +  by0的x0和y0,
也就是求出了满足a‘x0  +  b‘y0  =  1的一组整数解。因此可得: 
x  =  n/d  *  x0  +  b/d  *  t 
y  =  n/d  *  y0  -  a/d  *  t 
(t是整数)  
*/

欧几里得模板:

__int64 gcd(__int64 a,__int64 b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}辗转相除,原理:    定理:gcd(a,b) = gcd(b,a mod b)    证明:a可以表示成a = kb + r,则r = a mod b           假设d是a,b的一个公约数,则有    d|a, d|b,而r = a - kb,因此d|r    因此d是(b,a mod b)的公约数          假设d 是(b,a mod b)的公约数,则    d | b , d |r ,但是a = kb +r    因此d也是(a,b)的公约数    因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得         求(481,221)的最大公约数a=481,b=221;        (221,39)        (39,26)        (26,13)        (13,0)故最大公约数为13; void extend_gcd(__int64 a,__int64 b)
{
    if(b==0)
    {
        t=1;
        p=0;
    }
    else
    {
        extend_gcd(b,a%b);
         __int64 temp=t;
        t=p;
        p=temp-a/b*p;
    }

}欧几里得扩展推导:
把这个实现和Gcd的递归实现相比,发现多了下面的x,y赋值过程,这就是扩展欧几里德算法的精髓。
   可以这样思考: 
  对于a‘ = b, b‘ = a % b 而言,我们求得 x, y使得 a‘x + b‘y = Gcd(a‘, b‘) 
  由于b‘ = a % b = a - a / b * b (注:这里的/是程序设计语言中的除法) 
  那么可以得到: 
  a‘x + b‘y = Gcd(a‘, b‘) ===> 
  bx + (a - a / b * b)y = Gcd(a‘, b‘) = Gcd(a, b) ===>    ay +b(x - a / b*y) = Gcd(a, b) 
  因此对于a和b而言,他们的相对应的p,q分别是 y和(x-a/b*y)