题目链接:http://poj.org/problem?id=1061
其实欧几里得我一直都知道,只是扩展欧几里得有点蒙,所以写了一道扩展欧几里得裸题。
欧几里得算法就是辗转相除法,求两个数的最大公约数,算法是,a,b的最大公约数是gcd(b,a%b)然后不断递归下去,直到b=0
转换成c++语言就是
int ex_gcd(int a,int b)
{
if(b==)return a;
return ex_gcd(b,a%b);
}
扩展欧几里得就是假设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)
有了这一个式子我们就不难推出扩展欧几里得算法的代码了
int ex_gcd(int a,int b)
{
if(b==){
x=;y=;return a;
}
int d=ex_gcd(b,a%b);
int x1=;
x=y;
y=x1-(a/b)*y;
return d;
}//x,y是全局变量
然后知道了扩展欧几里得算法,就可以做这一道题了。
这道题基本就是模板,不用多说,用心体会。。。。
上代码Orz
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm> using namespace std; __int64 n,m,x,y,s,t,d,l,k,ans; __int64 ex_gcd(__int64 a,__int64 b)
{
if(b==)
{
x=;y=;return a;
}
__int64 r=ex_gcd(b,a%b);
__int64 tt=x;
x=y;
y=tt-a/b*y;
return r;
} int main()
{
scanf("%d%d%d%d%d",&s,&t,&n,&m,&l);
k=n-m;ans=t-s;
if(k<){
k=m-n;ans=s-t;
}
d=ex_gcd(k,l);
if(ans%d){
printf("Impossible");return ;
}
__int64 T=l/d;//T是周期,即两只青蛙每相对跳一圈的步数
ans=ans/d;//ans是一开始的距离,先看跳到相同位置步数
ans=ans*x;
ans=(ans%T+T)%T;//跳的步数对周期取余,+T再取余是为了避免负数
printf("%I64d",ans);
}
数据有些大,最好开__int64或者long long (我用__int64过的,没有试过long long 不过应该可以过)