`
dogasshole
  • 浏览: 836309 次
文章分类
社区版块
存档分类
最新评论

扩展欧几里得&&青蛙的约会

 
阅读更多
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙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"
唉,证明太枯燥无味了,先说一下题意吧。。。。。。
公青蛙一开始在x位置,母青蛙在y位置。公青蛙每次跳m米,母青蛙每次跳n米,并且都是向右跳的。地球经线长度是L,然后地球是圆的,也就是说,跳到L、L+1、L+2……其实就是跳到0、1、2。 公青蛙想追母青蛙,问多少次后它们能跳到一起。如果它们永远不能相遇,就输出Impossible(好可怜啊!)
很明显嘛,就是求一个k,使x + k*m ≡ y + k*n (mod L) 嘛,木有错吧?至少我是这么想滴!然后对方程化简咯,就变成(n-m) * k ≡ x-y (mod L)咯。然后这个方程其实就等价于(n-m)*k + L*s = x-y咯。这就是ax + by = c求整数x的模型。
要求ax + by = c的整数x解,可不是那么简单滴,不然我就不用花了一整个晚上时间了!首先,设d = gcd(a, b),方程两边除以d得到a/d * x + b/d * y = c/d,很显然嘛,a是整除d的,b也是整除d的,而x、y都是整数解,所以要求c/d也是整数嘛。如果c不整除d,当然就是Impossible咯。不然的话,如果我们能求出ax0+by0=d的解x0和y0,那么两边乘以c/d即a(c/d * x0) + b(c/d * y0) = c,就可以得到原来方程的解x = (c/d * x0),y = (c/d * y0)咯。
喂喂喂,等一下,你又怎么知道ax0 + by0 = d一定有解呢?这就得通过严谨的证明了:
定理一:如果d = gcd(a, b),则必能找到正的或负的整数k和l,使d = a*k + b*l。
证明:由于 gcd(a, 0) = a,我们可假设b ≠ 0,这样通过连除我们能够写出
a = b*q1 + r1
b = r1*q2 + r2
r1 = r2*q3 + r3
……
由第一式有r1 = a - q1*b,所以r1能写成k1*a + l1*b的形式(这时k1 = 1, l1 = -q1)。由第二式有r2 = b - r1*q2 = b - (k1*a + l1*b)*q2 = -q2*k1*a + (1 - q2*l1)*b = k2*a + l2*b。
显然,这过程通过这一串余数可重复下去,直到得到一个表达式rn = k*a + l*b,也就是d = k*a + l*b,这就是我们所要证明的。
所以说咯,ax0 + by0 = d一定有解!那么应该怎么求x0和y0呢?要用到一种叫做扩展欧基里得的算法(NND,第一次听说,我还是太弱了啊~~~)!
求法如下:由于gcd(a, b) = gcd(b, a%b) (这个不用证明了吧???地球人都知道!),有ax0 + by0 = gcd(a, b) = gcd(b, a%b) = bx1 + (a%b)y1,而a%b又可以写成a-a/b*b(a/b*b不等于a啊!记得为了这个SB问题还被骂过~),所以=bx1 + (a-a/b*b)y1 = ay1 + b(x1-a/b*y1),所以如果我们求出gcd(b, a%b) = bx1 + (a%b)y1的x1和y1,那么通过观察就可以求出x0 = y1,y0 = (x1 - a/b*y1)。那我们怎样求x1和y1呢?当然是求x2和y2了,做法一样滴。一直求到gcd(an, 0) = an*xn + 0 * yn,这时令xn=1,yn=0就完事了,就可以求xn-1和yn-1,然后xn-2和yn-2,然后一直求到x0和y0了。
所以得到ax0 + by0 = gcd(a, b)求整数x0、y0的扩展欧基里得算法(到这里烦到死啊!我做到这一步都差不多要放弃了!)
那么怎样求最小的非负整数x呢?
如果要求的解x 是最小正整数的话 有个简便方法。
a*x+b*y=gcd(a,b)两边同时除以gcd(a,b)得
a1*x+b1*y=1 这时a1与b1是互质的。
设最小正整数解为x1,对应的y为y1
a1*x1+b1*y1=1
a1*x+b1*y=1 a1*x1+b1*y1=1这两式相减得
a1*(x-x1)=b1*(y-y1).。因为a1 b1互质
所以x-x1=kb1 y-y1=ka1
所以x和x1对b1同余。。
所以x1=(x%b1+b1)%b1
详细证明如下:
又要用到两个定理:
定理二:若gcd(a, b) = 1,则方程ax ≡ c (mod b)在[0, b-1]上有唯一解。
证明:由定理一知,总可以找到或正或负的整数k和l使a*k + b*l = gcd(a, b) = 1,即我们可以求出ax ≡ 1 (mod b)的解x0。当然,两边乘以c有a(cx0) ≡ c (mod b),所以有x = cx0就是ax ≡ c (mod b)的解。由于加上或减去若干倍b都是该方程的解,所以x在[0, b-1]上有解。那么怎样确定它的唯一性呢?我花了一个小时终于证明出来了,证明方法就是,假设x1和x2都是[0, b-1]上的解,那么就有ax1 ≡ c (mod b),ax2 ≡ c (mod b),两式相减就有a(x1-x2) ≡ 0 (mod b),即a(x1-x2)可以被b整除。但gcd(a, b) = 1啊!所以a和b之间没有共同的语言可以交流,所以只能说(x1-x2)被b整除了。但x1和x2都在[0, b-1]上,所以x1-x2也在[0, b-1]上,所以只能说x1-x2=0了,因此x1=x2。这就证明了解的唯一性!
这个定理不过是为了证明定理三方便而已,定理三才是王道:
定理三:若gcd(a, b) = d,则方程ax ≡ c (mod b)在[0, b/d - 1]上有唯一解。
证明:上面说过,这个该死的方程等价于ax + by = c,如果有解,两边同除以d,就有a/d * x + b/d * y = c/d,即a/d * x ≡ c/d (mod b/d),显然gcd(a/d, b/d) = 1,所以由定理二知道x在[0, b/d - 1]上有唯一解。所以ax + by = c的x在[0, b/d - 1]上有唯一解,即ax ≡ c (mod b)在[0, b/d - 1]上有唯一解,得证!
有了上面几个该死的定理,小菜我终于把最小非负整数的问题解决了。如果得到ax ≡ c (mod b)的某一特解X,那么我令r = b/gcd(a, b),可知x在[0, r-1]上有唯一解,所以我用x = (X % r + r) % r就可以求出最小非负整数解x了!(X % r可能是负值,此时保持在[-(r-1), 0]内,正值则保持在[0, r-1]内。加上r就保持在[1, 2r - 1]内,所以再模一下r就在[0, r-1]内了)。
这么多证明这么多话语却只换来了21行代码,无奈啊!人生苦短啊!ACM,想说爱你不容易!下面果断贴代码:



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics