您的位置: 首页  >  IT文章  >  [poj1061]青蛙的约会<扩展欧几里得>

[poj1061]青蛙的约会<扩展欧几里得>

分类: IT文章 • 2022-08-01 13:55:15

题目链接：http://poj.org/problem?id=1061

其实欧几里得我一直都知道，只是扩展欧几里得有点蒙，所以写了一道扩展欧几里得裸题。

欧几里得算法就是辗转相除法，求两个数的最大公约数，算法是，a，b的最大公约数是gcd（b,a%b）然后不断递归下去，直到b=0

转换成c++语言就是

1 int ex_gcd(int a,int b)
2 {
3      if(b==0)return a;
4      return ex_gcd(b,a%b);        
5 }
View Code

扩展欧几里得就是假设c=gcd(a,b);则有a*x+b*y=c;

然后我们要做的就是求x，y，我就是这个位置一直有一点晕，但是这种情况其实简单的举个例子就可以得出结论了。

假设a=60,b=45,不难看出gcd(60,45)=15;然后也可以看出x=-2.y=3;

这是一眼可以看出来的，那么递归怎么做，我们先正常的gcd下去

gcd(60,45)--->gcd(45,15)--->gcd(15,0);

这是普通的gcd，然后把x，y带进去我们其实可以想到，当gcd到最后一步即b=0时，一定有x0=1,y0=0，用递归再返回来一层一层求出x,y；那递归的两层之间x，y有什么联系？

gcd(60,45)--->x=-2,y=3;

gcd(45,15)--->x1=1,y1=-2;

然后我们用式子来表示

gcd(a,b)=c=a*x+b*y

gcd(b,a%b)=c=b*x1+a%b*y1

a%b=a-(a/b)*b

a*x+b*y=b*x1+(a-(a/b)*b)*y1=b*x1+a*y1-(a/b)*b*y1=a*y1+b*(x1-(a/b)*y1);

从这里可以分析出来，

x=y1;

y=x1-(a/b*y1)

有了这一个式子我们就不难推出扩展欧几里得算法的代码了

 1 int ex_gcd(int a,int b)
 2 {
 3      if(b==0){
 4            x=1;y=0;return a;
 5      }
 6      int d=ex_gcd(b,a%b);
 7      int x1=1; 
 8      x=y;
 9      y=x1-(a/b)*y;
10      return d;
11 }//x,y是全局变量
12
View Code

然后知道了扩展欧几里得算法，就可以做这一道题了。

这道题基本就是模板，不用多说，用心体会。。。。

上代码Orz

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<iostream>
 6 #include<algorithm>
 7 
 8 using namespace std;
 9 
10 __int64 n,m,x,y,s,t,d,l,k,ans;
11 
12 __int64 ex_gcd(__int64 a,__int64 b)
13 {
14     if(b==0)
15     {
16         x=1;y=0;return a;
17     }
18     __int64 r=ex_gcd(b,a%b);
19     __int64 tt=x;
20     x=y;
21     y=tt-a/b*y;
22     return r;
23 }
24 
25 int main()
26 {
27     scanf("%d%d%d%d%d",&s,&t,&n,&m,&l);
28     k=n-m;ans=t-s;
29     if(k<0){
30         k=m-n;ans=s-t;
31     }
32     d=ex_gcd(k,l);
33     if(ans%d){
34         printf("Impossible");return 0;
35     }
36     __int64 T=l/d;//T是周期，即两只青蛙每相对跳一圈的步数 
37     ans=ans/d;//ans是一开始的距离，先看跳到相同位置步数 
38     ans=ans*x; 
39     ans=(ans%T+T)%T;//跳的步数对周期取余，+T再取余是为了避免负数 
40     printf("%I64d",ans);
41 }
View Code

数据有些大，最好开__int64或者long long （我用__int64过的，没有试过long long 不过应该可以过）

相关推荐