BZOJ传送门
luogu免权限地址
扩展欧几里得算法，由题可列(x+m∗t)≡(y+n∗t)(modL)，其中t为所求
由同余性质得：(x+m∗t)−(y+n∗t)=Lk
变形得：(n−m)t+lk=x−y，则转换为ax+by=c的形式
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ms(i,j) memset(i,j, sizeof i);
#define ll long long
using namespace std;
ll x,y,m,n,L;
ll gcd(ll a, ll b) {return b==0 ? a:gcd(b,a%b);}
ll abss(int x){return x<0 ? -x : x;}
ll e_gcd(ll a, ll b, ll &x, ll &y)
{
if (b==0)
{
x=1;
y=0;
return a;
}
ll ans = e_gcd(b,a%b,x,y);
ll temp = x;
x = y;
y = temp-a/b*y;
return ans;
}
ll cal()
{
ll a = n-m, b = L, c = x-y;
ll g = gcd(a,b);
if (c%g!=0) {printf("Impossible");exit(0);}//无解
a /= g; b /= g; c /= g;
e_gcd(a,b,x,y);
b = abss(b);//重要
x=((x*c)%b+b)%b; //求值
return x;
}
int main()
{
scanf("%lld%lld%lld%lld%lld", &x,&y,&m,&n,&L);
ll ans = cal();
printf("%lld\n", ans);
return 0;
}