爱悠闲 > poj1061

poj1061

标签: div,output,input  |  作者: weixinding 相关  |  发布日期 : 2015-02-14  |  热度 : 1406°

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


拓展欧几里得的应用,解二元一次不定方程的最小正整数解

首先是拓展欧几里得

令ax0+by0=gcd(a,b)

则bx1+(a%b)y1=gcd(b,a%b)

gcd(a,b)=gcd(b,a%b)

ax0+by0=bx1+(a%b)y1

由于a%b=a-a div b * b

ax0+by0=bx1+(a-a div b * b)y1

整理一下

ax0+by0=ay1+b(x1-a div b * y1)

对应系数

x0=y1

y0=x1-a div b * y1

所以只要知道方程的一个解,就可逆带得出原解

对于迭代下去

必然会有

X (xn)+gcd(a,b)yn=gcd(a,b)

显然,xn=0,yn=1

然后就可得出原方程的一组解


再来拓展到一般的方程

对于形如

ax+by=d

设gcd(a,b)=z

则有

ax0+by0=z

联立一下

用第二个式子*d/z

就有

(a/z)(x0*d)+(b/z)*(y0*d)=d

对应一下系数

x=x0*d/z,y=y0*d/z

要求的是整数解

所以d必须可以被z整除(d mod z = 0)

否则无整数解


这样便得出了一组正整数解

最后是求最小正整数解

ax+by=d

x如果增加b/z,则ax增加ab/z,

则by应减少ab/z,则y减少a/z

所以x的最小正整数解为x mod (b/z)


=、=是能推出来不假啦……

program poj1061;
type
  ass=record
        x,y:int64;
      end;
var
  i,j,k:longint;
  a,b,d,x,y,m,n,l,answer,temp:int64;
  ans:ass;
function min (a,b:int64):int64;
begin
  if a<b then exit(a)
         else exit(b);
end;
function gcd (a,b:int64):int64;
begin
  if a mod b = 0 then exit(b)
                 else exit(gcd(b,a mod b));
end;
function extgcd (a,b:int64):ass;
var
  temp:ass;
begin
  if b=0 then
    begin
      temp.x:=1;
      temp.y:=0;
      exit(temp);
    end;
  temp:=extgcd(b,a mod b);
  extgcd.x:=temp.y;
  extgcd.y:=temp.x-a div b * temp.y;
end;
begin
  read(x,y,m,n,l);
  a:=m-n;
  b:=y-x;
  ans:=extgcd(a,l);
  d:=gcd(a,l);
  if b mod d<>0 then
    begin
      writeln('Impossible');
      exit;
    end;
  answer:=ans.x*(b div d) mod (l div d);
  if answer<0 then answer:=answer+abs(answer) div abs(l div d);
  if answer<0 then answer:=answer+abs(l div d);
  writeln(answer);
end.