根据题目大意,设答案为 \(k\) ,不难列出式子:
\[x+km \equiv y+kn \pmod L \]移项,得
\[x-y \equiv kn-km \pmod L \] \[kn-km \equiv x-y \pmod L \]合并同类项
\[(n-m)k \equiv x-y \pmod L \]显然这就是一个线性同余方程,先把它变成一个不定方程
\[(n-m)k+Lr=(x-y) \]exgcd 得出 \(k\) 即可
代码:
#include<cstdio>
using namespace std;
//#define debug
typedef long long ll;
typedef long long Type;
inline ll abs(int x){ return x>0?x:-x; }
inline Type read(){
Type sum=0;
int flag=0;
char c=getchar();
while((c<'0'||c>'9')&&c!='-') c=getchar();
if(c=='-') c=getchar(),flag=1;
while('0'<=c&&c<='9'){
sum=(sum<<1)+(sum<<3)+(c^48);
c=getchar();
}
if(flag) return -sum;
return sum;
}
ll gcd(ll x,ll y){
if(x%y==0) return y;
return gcd(y,x%y);
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=1,y=0; return; }
exgcd(b,a%b,x,y);
ll t=x; x=y;
y=t-(a/b)*y;
return;
}
inline ll LiEu(ll a,ll b,ll p){
if(a<0) a=-a,b=-b;
b=(b%p+p)%p;
if(b%gcd(a,p)) return -1;
ll x,y,r;
exgcd(a,p,x,y);
x=x*(b/gcd(a,p));
r=p/gcd(a,p);
return (x%r+r)%r;
}
ll x,y,m,n,l,ans;
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
x=read(); y=read(); m=read(); n=read(); l=read();
if(x==y) return printf("Impossible"),0;
ans=LiEu(n-m,x-y,l);
if(ans==-1) return printf("Impossible"),0;
printf("%lld",ans);
return 0;
}