poj1061 扩展欧几里得

/*
Time:2019.11.3
Author: Goven
type：扩展欧几里得 
err:
ref:不会：https://www.cnblogs.com/comeon4mydream/archive/2011/07/18/2109060.html
知识点：3个定理+扩展欧几里得求解 
*/
#include<iostream>

using namespace std;
typedef long long ll;

ll extgcd(ll a, ll b, ll &x, ll &y){//扩展欧几里得，求解a*x+b*y = c中x值(a,b,c已知) 
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    ll d, t;
    d = extgcd(b, a % b, x, y);
    t = x - a / b * y; x = y; y = t;
    return d;
}
int main()
{
    ll x, y, m, n, L, d, X, Y, r;
    while (cin >> x >> y >> m >> n >> L) {
        d = extgcd(n - m, L, X, Y); r = L / d;
        if ((x - y) % d) cout << "Impossible" << endl;
        else cout << (X * (x - y) / d % r + r) % r << endl;
    }
    
    return 0;
}

当extgcd中a, b为负数时，d为负数，求解结果取余的时候需要对mod进行绝对值求解：

/*
Time:2019.12.14
Author: Goven
type：扩展欧几里得 
ref:
*/
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;

ll ext_gcd (ll a, ll b, ll &x, ll &y) {//att1:a, b的值可以小于0，返回的d也可能小于0 
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = ext_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    ll x, y, m, n, L;
    cin >> x >> y >> m >> n >> L;
    ll c = y - x;
    ll d = ext_gcd(m - n, L, x, y);
    if (c % d) {
        cout << "Impossible" << endl;
        return 0;
    } 
    x *= c / d;
    ll mod = abs(L / d);//err1:d可能小于0，所以要取绝对值 
    x = (x % mod + mod) % mod;
    cout << x << endl;
    return 0;
}