求解形如ax+by=c的不定方程
#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
LL extend_gcd(LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
LL d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
LL n, m, x, y, l;
cin >> x >> y >> m >> n >> l;
LL a = n - m, c = x - y;
if (a < 0)
{
a = -a;
c = -c;
}
LL d = extend_gcd(a, l, x, y);
if (c % d != 0)
cout << "Impossible";
else
cout << ((x * (c / d)) % (l / d) + (l / d)) % (l / d);
return 0;
}