[ZJOI 2002] 青蛙的约会

知识点

线性同余方程、扩展欧几里得

解题思路

碰面条件为x+mt≡y+nt(mod L)，即(m-n)t≡y-x(mod L)。把速度差规范为非负，令g=gcd(m-n,L)。若g不整除位置差则无解；否则用扩展欧几里得求系数，再对L/g规范化，得到最小非负次数。

正确性说明

两蛙坐标相同模L当且仅当上述线性同余成立。整数方程可解当且仅当g整除常数项；除以g后系数互素，解构成模L/g的一个剩余类，最小非负代表即最早相遇时间。

易错点

速度相同也要通过gcd条件处理；位置差可能负；需要约掉g后对L/g取模；乘积用128位中间值避免溢出。

复杂度

时间O(log L)，递归空间O(log L)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
long long ex(long long a,long long b,long long&x,long long&y){if(!b){x=1;y=0;return a;}long long u,v,g=ex(b,a%b,u,v);x=v;y=u-a/b*v;return g;}int main(){long long x,y,m,n,L;cin>>x>>y>>m>>n>>L;long long a=m-n,c=y-x;if(a<0)a=-a,c=-c;long long u,v,g=ex(a,L,u,v);if(c%g){cout<<"Impossible\n";return 0;}long long mod=L/g;__int128 z=(__int128)u*(c/g);long long ans=(long long)(z%mod);if(ans<0)ans+=mod;cout<<ans<<'\n';}