HDU----专题训练

Problem A

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 26   Accepted Submission(s) : 15

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

此题为欧几里得扩展的问题:

  有题目的意思,不难想到,若果两者相遇。。。那么必须满足 x+k*m+w*L= y+k*n+r*L;

  通过化解得  k*(m-n)+q*L=y-x;  (需要注意的是q 为w , r 的 合集 的结果,但是由于w,r,两者是不知道的,所以我们不妨用一个q来取代),这样他就有了,那个谁的影子,没错,像不像

  x*a+b*y=c;  由于 x*a+b*y=c=gcd(a,b); 但是所得到的公约数.....又

定理一:如果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了。

定理二:若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]内了)。

 1 #include<iostream>
 2 using namespace std;
 3 long long x,y,q;
 4 void exgcd(long long a,long long b)
 5 {
 6     if(b==0)
 7     {
 8         x=1,y=0,q=a;
 9     }
10     else
11     {
12         exgcd(b,a%b);
13         long long temp=x;
14         x=y,y=temp-a/b*y;
15     }
16 }
17 int main()
18 {
19     long long X,Y,M,N,L;
20     while(cin>>X>>Y>>M>>N>>L)
21     { 
22         exgcd(N-M,L);
23         if((X-Y)%q)
24             cout<<"Impossible"<<endl;
25         else
26         {
27             long long temp=L/q;
28             cout<<((X-Y)/q*x%temp+temp)%temp<<endl;
29         }
30     }
31     return 0;
32 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

HDUOJ-------Being a Good Boy in Spring Festival

Being a Good Boy in Spring Festival Time Limit: 1000/1000 MS (Java/Others)    Me...

406130
来自专栏数据结构与算法

BZOJ4668: 冷战(并查集)

• 1 u v, Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第

9020
来自专栏Crossin的编程教室

【每周一坑】囚徒困境

本周的题目非常有意思,取于大名鼎鼎的 囚徒困境 。首先来看背景资料: “囚徒困境”是1950年美国兰德公司的梅里尔·弗勒德(Merrill Flood)和梅尔文...

41080
来自专栏大数据钻研

Java设计模式之装饰模式趣谈

JVM:”上次给我招的工人不错啊!” oo程序员:”………..” JVM:”现在来我开的博物馆生意越来越好了,原来”舞台剧”的方式已经不能满足顾客的需求了”...

28270
来自专栏小樱的经验随笔

元胞自动机实现多数分类算法

元胞自动机(Cellular automaton) 元胞自动机是由元胞组成的网格,每个元胞都根据邻域的状态来选择开或关。所有的元胞都遵循同样的规则,也称为元胞的...

36550
来自专栏ml

HDUOJ---2546 饭卡

饭卡 Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/O...

35850
来自专栏ml

HDUOJ-----2068RPG的错排

RPG的错排 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

31250
来自专栏数据结构与算法

洛谷P1516 青蛙的约会

题目描述 两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出...

35250
来自专栏前端说吧

JS-利用ajax获取json数据,并传入页面生成动态tab

40570
来自专栏ml

HDUOJ----2063过山车

过山车 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

34060

扫码关注云+社区

领取腾讯云代金券