POJ 1061 青蛙的约会【扩展欧几里德】

时间:2022-03-05 23:11:57

设跳的次数为t

根据题意可得以下公式:
(x+mt)%L=(y+nt)%L

变形得

(x+mt)-(y+nt)=kL

(n-m)t+kL=x-y

令a=(n-m),b=L,c=x-y

得 at+bk=c

此时就相当于求解二元不定方程ax+by=c的最小整数解

1、先计算Gcd(a,b),若n不能被Gcd(a,b)整除,则方程无整数解;否则,在方程两边同时除以Gcd(a,b),得到新的不定方程a' * x + b' * y = c',此时Gcd(a',b')=1;

2、利用欧几里德算法求出方程a' * x + b' * y = (gcd)1的一组整数解x0,y0,则c' * x0,c ' * y0是方程a' * x + b' * y = c'的一组整数解;

3、根据数论中的相关定理,可得方程a' * x + b' * y = c'的所有整数解为:

    x = c' * x0 + b' * t

    y = c' * y0 - a' * t
(t为整数)

上面的解也就是a * x + b * y = c 的全部整数解。

此时方程的所有解为:x=c'*x0+b'*t,x的最小的可能值是0,令x=0可求出当x最小时的t的取值,但由于x=0是可能的最小取值,实际上可能x根本取不到0,那么由计算机的取整除法可知:由 t=-c'*x0/b'算出的t,代回x=c'*x0+b'*t中。

得minx=c'*x0+b'*[-c'*x0/b']

[]表示向下取整。

设A=c'*x0

可得 minx=A-A/b'*b'=A%b'=(c'*x0)%b'

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll ex_gcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=,y=;
return a;
}
ll ans=ex_gcd(b,a%b,y,x);
y-=a/b*x;
return ans;
}
ll cal(ll a,ll b,ll c){
ll x,y;
ll d=ex_gcd(a,b,x,y);
if(c%d) return -;
b/=d,c/=d;
return ((x*c)%b+b)%b;
}
int main(){
ll x,y,v1,v2,l;
while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&v1,&v2,&l)!=EOF){
ll ans=cal(v2-v1,l,x-y);
if(ans==-) printf("Impossible\n");
else printf("%I64d\n",ans);
}
return ;
}

http://blog.sina.com.cn/s/blog_83d1d5c701014rm2.html