题目
思路
显然
x
+
k
m
+
q
L
=
y
+
k
n
x+km+qL=y+kn
x+km+qL=y+kn
=
>
k
(
n
−
m
)
+
q
L
=
y
−
x
=>k(n-m)+qL=y-x
=>k(n−m)+qL=y−x
然后exgcd即可(要判无解)
code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
long long n,m,x,y,l,ans;
long long gcd(long long x,long long y)
{
int r;
while (y!=0)
{
r=x%y;
x=y,y=r;
}
return x;
}
long long xx,yy;
long long exgcd(long long x,long long y,long long &xx,long long &yy)
{
if (!y)
{
xx=1,yy=0;
return x;
}
ans=exgcd(y,x%y,xx,yy);
long long t=xx;
xx=yy;
yy=t-x/y*yy;
return ans;
}
int main()
{
cin>>x>>y>>m>>n>>l;
n=n-m,x=x-y;
if (n<0)
{
n=-n,x=-x;
}
exgcd(n,l,xx,yy);
if (x%ans!=0) cout<<"Impossible";
else cout<<((xx*(x/ans))%(l/ans)+(l/ans))%(l/ans);
return 0;
}