题解

假设答案为a，其实就是求解：，化为。

对应到中，a = m-n，b = L， c = y-x。x为a，y为k。要求最小的非负整数x。

假设的一组解为(x0，y0)，那么通解为

所以最小非负解为。

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
void exgcd(LL a, LL b, LL& d, LL& x, LL& y)
{
    if (!b) { d=a; x=1; y=0; }
    else { exgcd(b, a%b, d, y, x); y -= x*(a/b); }
}
LL cal(LL a, LL b, LL c)
{
    LL GCD, x0, y0;
    exgcd(a, b, GCD, x0, y0);
    if (c%GCD) return -1;
    LL bb = b/GCD;
    bb = llabs(bb);//GCD可能为负数，需要把bb变为正
    x0 *= c/GCD; y0 *= c/GCD;
    return (x0%bb+bb)%bb;
}
int main()
{
    LL x, y, m, n, L; scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L);
    LL ans = cal(m-n, L, y-x); /// x+ma ≡ y+na (mod L) => (m-n)a + L*k = y-x;
    if (ans != -1) printf("%lld\n", ans);
    else printf("Impossible\n");
    return 0;
}
/*
1 2 3 4 5
*/