青蛙的约会 （同余，线性同余方程） HQG

线性同余方程） HQG"/>

青蛙的约会 （同余，线性同余方程） HQG

模拟样例易知 如果青蛙们走k步，则必有

km+x≡kn+y(mod k m + x ≡ k n + y ( m o d $km+x ≡kn+y (mod$ L) L ) $L)$

将该式化简，

−>(m−n)∗k≡y−x(mod − > ( m − n ) ∗ k ≡ y − x ( m o d $->(m-n)*k ≡y-x (mod$ L) L ) $L)$

−>ak≡b(modL) − > a k ≡ b ( m o d L ) $->ak ≡b (mod L)$

之后参见NOIp2012 同余方程 的做法即可（提示，exgcd）

最后不忘处理负数的情况

搓的代码

#include <bits/stdc++.h>
using namespace std ;typedef long long ll ;ll x,y,m,n,L; ll exgcd(ll a,ll b,ll &x,ll &y){if (b==0){x=1 ;y=0 ;return a ;}else {ll ans=exgcd(b,a%b,y,x) ;y-=(a/b)*x ; return ans ;}
}int main(){scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L) ;ll b=n-m ;ll a=x-y ;if (b<0){a=-a ;b=-b ;} ll c=exgcd(b,L,x,y) ;if (a%c!=0) printf("Impossible\n") ;else printf("%lld\n",((x*(a/c))%(L/c)+(L/c))%(L/c)) ;
}