拓展欧几里得算法

2024-08-12

求解形如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;
 }