Description
兩只青蛙在網(wǎng)上相識了，它們聊得很開心，于是覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止?？墒撬鼈兂霭l(fā)之前忘記了一件很重要的事情，既沒有問清楚對方的特征，也沒有約定見面的具體位置。不過青蛙們都是很樂觀的，它們覺得只要一直朝著某個(gè)方向跳下去，總能碰到對方的。但是除非這兩只青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個(gè)程序來判斷這兩只青蛙是否能夠碰面，會在什么時(shí)候碰面。
我們把這兩只青蛙分別叫做青蛙A和青蛙B，并且規(guī)定緯度線上東經(jīng)0度處為原點(diǎn)，由東往西為正方向，單位長度1米，這樣我們就得到了一條首尾相接的數(shù)軸。設(shè)青蛙A的出發(fā)點(diǎn)坐標(biāo)是x，青蛙B的出發(fā)點(diǎn)坐標(biāo)是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩只青蛙跳一次所花費(fèi)的時(shí)間相同。緯度線總長L米?，F(xiàn)在要你求出它們跳了幾次以后才會碰面。

Input
輸入只包括一行5個(gè)整數(shù)x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
Output
輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行"Impossible"
Sample Input
1 2 3 4 5
Sample Output
4

解如下：
就是擴(kuò)展歐幾里德算法－求解不定方程，線性同余方程。　　設(shè)過s步后兩青蛙相遇，則必滿足以下等式：
　　　　(x+m*s)-(y+n*s)=k*l(k=0,1,2....)
　　稍微變一下形得：
　　　　(n-m)*s+k*l=x-y
     令n-m=a,k=b,x-y=c,即
　　　　a*s+b*l=c
　　只要上式存在整數(shù)解，則兩青蛙能相遇，否則不能。
　　首先想到的一個(gè)方法是用兩次for循環(huán)來枚舉s,l的值，看是否存在s,l的整數(shù)解，若存在則輸入最小的s，
但顯然這種方法是不可取的，誰也不知道最小的s是多大，如果最小的s很大的話，超時(shí)是明顯的。
　　其實(shí)這題用歐幾里德擴(kuò)展原理可以很快的解決，先來看下什么是歐幾里德擴(kuò)展原理：
　　歐幾里德算法又稱輾轉(zhuǎn)相除法，用于計(jì)算兩個(gè)整數(shù)a,b的最大公約數(shù)。其計(jì)算原理依賴于下面的定理：
　　定理：gcd(a,b) = gcd(b,a mod b)
　　證明：a可以表示成a = kb + r，則r = a mod b
　　假設(shè)d是a,b的一個(gè)公約數(shù)，則有
　　d|a, d|b，而r = a - kb，因此d|r
　　因此d是(b,a mod b)的公約數(shù)
　　假設(shè)d 是(b,a mod b)的公約數(shù)，則
　　d | b , d |r ，但是a = kb +r
　　因此d也是(a,b)的公約數(shù)
　　因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證
　　歐幾里德算法就是根據(jù)這個(gè)原理來做的，其算法用C++語言描述為：　
　　int Gcd(int a, int b)
　　{
     　　if(b == 0)
         　　return a;
     return Gcd(b, a % b);
　　}
　　當(dāng)然你也可以寫成迭代形式：
　　int Gcd(int a, int b)
　　{
     　　while(b != 0)
     　　{
         　　int r = b;
　　         b = a % b;
     　　     a = r;
     　　}
     　　return a;
　　}
　　本質(zhì)上都是用的上面那個(gè)原理。
　　補(bǔ)充: 擴(kuò)展歐幾里德算法是用來在已知a, b求解一組x，y使得a*x+b*y=Gcd(a,b)(解一定存在，根據(jù)數(shù)論中的相關(guān)定理)。擴(kuò)展歐幾里德常用在求解模線性方程及方程組中。下面是一個(gè)使
用C++的實(shí)現(xiàn)：
　　int exGcd(int a, int b, int &x, int &y)
　　{
     　　if(b == 0)
     　　{
         　　x = 1;
         　　y = 0;
       　　 return a;
     　　}
     　　int r = exGcd(b, a % b, x, y);
     　　int t = x;
     　　x = y;
     　　y = t - a / b * y;
　　     return r;
　　}
　　把這個(gè)實(shí)現(xiàn)和Gcd的遞歸實(shí)現(xiàn)相比，發(fā)現(xiàn)多了下面的x,y賦值過程，這就是擴(kuò)展歐幾里德算法的精髓。
　　可以這樣思考:
　　對于a' = b, b' = a % b 而言，我們求得 x, y使得 a'x + b'y = Gcd(a', b')
　　由于b' = a % b = a - a / b * b (注：這里的/是程序設(shè)計(jì)語言中的除法)
　　那么可以得到:
　　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而言，他們的相對應(yīng)的p，q分別是 y和(x-a/b*y).
　　在網(wǎng)上看了很多關(guān)于不定方程方程求解的問題，可都沒有說全，都只說了一部分，看了好多之后才真正弄清楚不定方程的求解全過程，步驟如下：
　　求a * x + b * y = n的整數(shù)解。
　　1、先計(jì)算Gcd(a,b)，若c不能被Gcd(a,b)整除，則方程無整數(shù)；否則，在方程兩邊同時(shí)除以Gcd(a,b)，得到新的不定方程a' * x + b' * y = n'，此時(shí)Gcd(a',b')=1;
     2、利用上面所說的歐幾里德算法求出方程a' * x + b' * y = 1的一組整數(shù)解x0,y0，則n' * x0,n' * y0是方程a' * x + b' * y = n'的一組整數(shù)解；
　　3、根據(jù)數(shù)論中的相關(guān)定理，可得方程a' * x + b' * y = n'的所有整數(shù)解為：
         x = n' * x0 + b' * t
y = n' * y0 - a' * t
(t為整數(shù))
　　　 上面的解也就是a * x + b * y = n 的全部整數(shù)解。
　　下面來看看我這題的代碼：
　　# include <stdio.h>
　　__int64 gcd(__int64 a,__int64 b)//求a,b的最大公約數(shù)
　　{
if(b==0)
   return a;
return gcd(b,a%b);
　　}
　　void exgcd(__int64 a,__int64 b,__int64 &m,__int64 &n)//求a * x + b * y = Gcd(a,b)的一組整數(shù)解，結(jié)果儲存在m,n中
　　{
if(b==0)
{
   m=1;
   n=0;
   return ;
}
exgcd(b,a%b,m,n);
__int64 t;
t=m;
m=n;
n=t-a/b*n;
　　}
　　int main()
　　{
__int64 x,y,m,n,l,a,b,c,k1,k2,r,t;
while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l)!=EOF)
{
   a=n-m;
   b=l;
   c=x-y;
   r=gcd(a,b);
   if(c%r)//如果c不能被r整除，則由數(shù)論中的相關(guān)定理可知整數(shù)解一定不存在
   {
     printf("Impossible\n");
     continue;
   }
   a/=r;
   b/=r;
   c/=r;
   exgcd(a,b,k1,k2);//求a*k1+b*k2=Gcd(a,b)的整數(shù)解，此時(shí)Gcd(a,b)=1
   t=c*k1/b;//見注1
   k1=c*k1-t*b;
   if(k1<0)
     k1+=b;
   printf("%I64d\n",k1);
}
return 0;
　　}