POJ 青蛙的约会 (扩展欧几里得)

青蛙的约会

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)

Total Submission(s) : 2 Accepted Submission(s) : 2

Problem 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

Source

PKU

详细解法：http://www.cnblogs.com/comeon4mydream/archive/2011/07/18/2109060.html

http://www.cnblogs.com/jian1573/archive/2012/07/22/2603943.html

首先我们先讨论欧几里得算法（ gcd ):

gcd( a, b )即求两个数的最大公约数

递归算法：

int gcd( int a, int b ) { 　　return b==0?a:gcd( b, a%b ); //gcd(a,b) = gcd(a%b,b)，这个递归一次以后就终止了无法保证a b可以继续减小，所以把 b 和 a%b交换顺序。 }

非递归算法：

int gcd( int a, int b ) { 　　if( b==0 )return 0; 　　while(b) 　　{ 　　　　int t=a%b; 　　　　a=b; 　　　　b=t; 　　} 　　return a;

}

现在我们讨论算法的正确性，即证明gcd(a,b)==gcd(b,a%b),我们只要证明gcd(a,b)==gcd(a-b,b)即可，因为可以由此逐步扩展为gcd(a,b) == gcd(a-k*b,b),而 gcd(a-k*b,b)==gcd(a%b,b)。因为a,b的公约数必然是a-b,b的公约数故 gcd(a,b) <= gcd(a-b,b);另a-b b的公约数也必然是a b的公约数，gcd(a,b) >= gcd(a-b,b).所以gcd(a,b) == gcd(a-b,b)。

再说扩展欧几里得:

扩展欧几里德算法是用来求解a*x+b*y==gcd(a,b)这样的方程的。同样利用gcd(a,b)==gcd(b,a%b)把a*x+b*y==gcd( a, b )转化为b*x'+(a%b)*y'==gcd( b, a%b );

根据递归的思想，假设现在我们已经求出了x' y',剩下的关键就是如何用x' y'求出x y.我们观察gcd(b,a%b) = b*x'+(a%b)*y'，只要把右边重新写成 a*x+b*y 的形式就行了，所以需要对b*x'+（a%b）*y'进行变形，因为a%b == a-a/b*b,故b*x'+(a%b)y' = b*x'+(a-a/b*b)y' == a*y' + b*(x'-a/b*y') .

这样便可得出 x = y' y = x'-a/b*y'。

所以扩展gcd的递归算法为

LL exgcd( LL a, LL b, LL &x, LL &y ) { 　　LL d, t; 　　if( b==0 ) 　　{ 　　　　x=1, y=0; 　　　　return a; 　　} 　　d=exgcd( b, a%b, x, y ); 　　t=x, x=y, y=t-a/b*y; 　　return d; 　　　　　　// 返回gcd( a, b ); }

这样我们就得到了方程的解 :

x==x0+b*t;　　　　// 特解+通解

y==y0+a*t;

然后再看一般形式 a*x+b*y==c;

当且仅当 c%gcd( a,b )==0时方程才有解。

a*x+b*y==c的求解可以先求出a*x+b*y=gcd(a,b),然后将x y扩大c/gcd(a,b)倍就可以了。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

long long Gcd(long long a,long long b){
    return b==0?a:Gcd(b,a%b);
}

void exGcd(long long a,long long b,long long &x,long long &y){
    if(b==0){
        x=1; y=0;
        return ;
    }
    exGcd(b,a%b,x,y);
    long long tmp=x;
    x=y;
    y=tmp-a/b*y;
}

int main(){

    //freopen("input.txt","r",stdin);

    long long x,y,m,n,L;
    long long a,c,k1,k2,r;
    while(~scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L)){
        a=n-m; c=x-y;
        r=Gcd(a,L);
        if(c%r){
            puts("Impossible");
            continue;
        }
        a/=r; L/=r; c/=r;
        exGcd(a,L,k1,k2);
        long long ans=c*k1-c*k1/L*L;
        if(ans<0)
            ans+=L;
        printf("%I64d\n",ans);
    }
    return 0;
}

#include <stdio.h>
 typedef long long LL;
 LL exgcd( LL a, LL b, LL &x, LL &y )
 {
     LL d, t;
     if( b==0 )
     {
         x=1, y=0;
         return a;    
     }
     d=exgcd( b, a%b, x, y );
     t=x, x=y, y=t-a/b*y;
     return d;
 }
 
 // (a+c*m)%2^k=b ==> c*m-n*2^k=b-a;
 int main( )  
 {  
     LL A,B,C,k, a, b, c, x, y, n;  
     while(scanf("%lld %lld %Illd %lld",&A,&B,&C,&k))  
     {  
         if(!A && !B && !C && !k)  
             break;  
   
         a=C, b=B-A, n=(LL)1<<k;  //2^k   
         LL d=exgcd(a,n,x,y);  //求a,n的最大公约数d=gcd(a,n)和方程d=ax+by的系数x、y  
         if(b%d!=0)  //方程 ax=b(mod n) 无解  
            puts("FOREVER"); 
         else  
         {  
             x=(x*(b/d))%n;  //方程ax=b(mod n)的最小解  
             x=(x%(n/d)+n/d)%(n/d);  //方程ax=b(mod n)的最整数小解  
             printf("%lld\n",x);  
         }  
     }  
     return 0;  
 }