题意是给你两只青蛙,在一个首位相连的数轴上跳,问能否碰到。给出x,y,n,m,l。分别代表第一只所在位置,第二只所在位置,第一只每次跳的步数,第二只每次跳的步数,以及数轴总长度。
稍微化简一下可以发现有 x+m*t=k1*L+p; y+n*t=k2*L+p
得到(n-m)*t+l*(k2-k1)=x-y
可以发现,这是一个二元一次方程,而我们就是要求一对整数解,且(t 是大于0的最小解)
所以就是一道扩展欧几里得算法。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) using namespace std; long long x,y,m,n,l,a,b,d,c; long long gcd(long long a, long long b) { return b == 0 ? a:gcd(b,a%b); } long long X,Y; void ex_gcd(long long a, long long b) { if (!b) { X=1; Y=0; return ; } ex_gcd(b,a%b); long long t = X; X = Y; Y = t - (a/b)*Y; } int main () { cin>>x>>y>>m>>n>>l; a=n-m; b=l; c=gcd(a,b); // cout<<"c="<<c<<endl; if ((x-y)%c == 0) { ex_gcd(a,b); X *= (x-y)/c; Y *= (x-y)/c; //// cout<<X<<" "<<Y<<endl; long long k=l/c; if (k<0) k=-k; if (X>=0) { X=X-((X/k)+1)*k; while(X<=0) { X+=k; } } else { X=X+((X/k)*(-1)+1)*k; } cout<<X<<endl; } else cout<<"Impossible"<<endl; return 0; }