[數論]POJ 1061 青蛙的約會 擴充歐幾裡得算法

傳送門：青蛙的約會

青蛙的約會

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 85205	Accepted: 14921

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

浙江

解題報告：

此題為擴充歐幾裡得算法。

根據題意，兩個青蛙跳到同一個點上才算是遇到了，是以有 (x+m*t) - (y+n*t) = p * ll;  (t是跳的次數，ll是a青蛙跳的圈數跟b青蛙的圈數之差。整個就是路程差等于緯度線周長的整數倍)，
轉化一下： (n-m) * t + ll * p = x – y;
令 a = n-m,  b = ll,  c = gcd(a, b),  d = x-y;
有 a * t + b * p = d;   (1)
要求的是t的最小整數解。
用擴充的歐幾裡德求出其中一組解t0 ,p0, 并令c = gcd(a, b);
有 a * t0 + b * p0 = c;  (2)
因為c = gcd(a, b), 是以 a * t / c是整數，b * t / c 也是整數，是以 d / c 也需要是整數，否則無解。
 (2)式兩邊都乘(d / c) 得 a * t0 *(d / c) + b * p0 * (d / c) = d;
 是以t0 * (d / c)是最小的解，但有可能是負數。
因為a * ( t0 *(d / c) + b*n) + b * (p0 * (d / c) – a*n) = d; (n是自然數)
是以解為 (t0 * (d / c) % b + b) % b;
           

代碼如下：

#include<iostream>
#include<cstdio>
using namespace std;
long long ext_gcd(long long a,long long b,long long &x,long long &y){
    if(b==0){
        x=1;y=0; return a;
    }
    long long d=ext_gcd(b,a%b,x,y);
    long long xt=x;
    x=y;
    y=xt-a/b*y;
    return d;
}
int main(){
    long long xx,yy,m,n,l;
    while(scanf("%lld%lld%lld%lld%lld",&xx,&yy,&m,&n,&l)==5){
        if(n==m){
            printf("Impossible\n");
            continue;
        }
        long long a,b,c,d,x,y;
        a=n-m;
        d=xx-yy;
        b=l;
        c=ext_gcd(a,b,x,y);
        if(d%c!=0){
            printf("Impossible\n");
            continue;
        }
        else{
            b=b/c;
            d=d/c;
            long long v=d*x;
            printf("%lld\n",(v%b+b)%b);
        }
    }
    return 0;
}