学步园

扩展欧几里德算法求的是二元一次方程ax+by=c，在a,b,c已知的情况下x的最小整数值，

扩展欧几里德算法:

int exgcd(int a,int b,int &X,int &Y)<br /> {<br /> if(b==0)<br /> {<br /> X=1;<br /> Y=0;<br /> return a;<br /> }<br /> int d=exgcd(b,a%b,X,Y);<br /> int t=X;<br /> X=Y;<br /> Y=t-(a/b)*Y;<br /> return d;<br /> }

int r=exgcd(a,b,X,Y)

当c%r==0时:

b/=r;

c/=r;

x的最小整数值x1=(c*X%b+b)%b

否则不存在x的最小整数解。

题目poj 1061

这题先列出式子，设跳了xi步之后他们会相遇。则有公式

(xi*m+x)-(xi*n+y)=kl(k=1,2,3.....)或者(xi*n+y)-(xi*m+x)=kl(k=1,2,3.....)

化简成xi(m-n)+kl=y-x或者xi(n-m)+kl=x-y。

刚好符合扩展欧几里德的公式要求，a=m-n(m>n)或者n-m(n>m),b=k,c=y-x(m>n)或者x-y(n>m)，这样套扩展欧几里德公式求xi的最小正整数就行了,代码

#include<iostream><br /> #include<cmath><br /> using namespace std;<br /> __int64 exgcd(__int64 a,__int64 b,__int64 &X,__int64 &Y)<br /> {<br /> if(b==0)<br /> {<br /> X=1;<br /> Y=0;<br /> return a;<br /> }<br /> __int64 d=exgcd(b,a%b,X,Y);<br /> __int64 t=X;<br /> X=Y;<br /> Y=t-(a/b)*Y;<br /> return d;<br /> }<br /> int main()<br /> {<br /> __int64 x,y,m,n,L,X,Y,a,b,r,x1,c;<br /> while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L)!=EOF)<br /> {<br /> a=m>n?m-n:n-m;<br /> b=L;<br /> c=m>n?y-x:x-y;<br /> r=exgcd(a,b,X,Y);<br /> if(c%r==0)<br /> {<br /> b/=r;<br /> c/=r;<br /> x1=(c*X%b+b)%b;<br /> printf("%I64d/n", x1);<br /> }<br /> else<br /> cout<<"Impossible"<<endl;<br /> }<br /> return 0;<br /> }<br />