POJ - 1061 扩展欧几里德算法+求最小正整数解

//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#pragma GCC optimize(2)
#include <algorithm>
#include <iostream>
#include<sstream>
#include<iterator>
#include<cstring>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>

using namespace std;

typedef double dou;
typedef long long ll;

#define M 100005
#define inf 0x3f3f3f3f
#define mod 1000000007  
#define left k<<1
#define right k<<1|1
#define W(a) while(a)  
#define ms(a,b) memset(a,b,sizeof(a))

ll gcd_pro(ll A, ll B, ll &x, ll &y) {
    if (B == 0) {
        x = 1, y = 0;
        return A;
    }
    ll ans = gcd_pro(B, A % B, y, x);
    y = y - (A / B) * x;
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);

    ll gcd;
    ll x, y;
    ll st_x, st_y, m, n, L;

    cin >> st_x >> st_y >> m >> n >> L;

    gcd = gcd_pro(m - n, L, x, y);

    if ((st_y - st_x) % gcd != 0) {
        cout << "Impossible" << endl;
    }
    else {
        x = x * (st_y - st_x) / gcd;
        L /= gcd;
        x %= L;
        if (x < 0) {
            if (L < 0)L = -L;
            x += L;
        }
        cout << x << endl;
    }

    return 0;
}