分析:如果两只青蛙能够相遇,则满足: (x+mt)-(y+nt)=p*L; t为跳的次数 则:x-y+(m-n)*t=p*L; 即:(m-n)≡(y-x)mod L 此线性同余方程有解当且仅当 gcd(m-n,L)|(y-x) 利用欧几里德求解ax+by=c即可,其中a=m-n,b=L,c=y-x 求出一个特解后,令d=gcd(a,b) 特解为:x0=c/d*x0 方程的所有解公式为x=(d/d*x0+L/d*i)(i=0,1,2,……,d-1) 最小解为(x0mod(L/d)+L/d)mod(L/d);
View Code
#includetypedef __int64 LL;LL extgcd(LL a,LL b,LL &x,LL &y){ if(!b) { x = 1; y = 0; return a; } LL g = extgcd(b,a%b,x,y); LL t = x; x = y; y = t - (a / b) * y; return g;}inline LL _abs(__int64 x){ return x > 0 ? x : -x;}bool modeq(LL a,LL c,LL m,LL &x){ LL g,y; g = extgcd(a,m,x,y); if( c%g ) return false; else { x = (c/g * x) % m; x %= _abs(m/g); if(x<0) x += _abs(m/g); return true; }}int main(){ LL x,y,m,n,L; LL A,C,M,X0; while(scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L)!=EOF) { A = m-n; C = y-x; M = L; if(modeq(A,C,M,X0)) printf("%I64d\n",X0); else printf("Impossible\n"); } return 0;}