cpp_src/number_theory/GaussGcd.cpp

View this file on GitHub
Last update: 2021-11-27 23:06:43+09:00

Code

ll near(ll x, ll d) {
    bool p = x >= 0;
    x = abs(x);
    ll t = x % d * 2 >= d ? x / d + 1 : x / d;
    if (!p) t = -t;
    return t;
}

pair<ll, ll> get(ll p, ll q, ll r, ll s) {
    if (r == 0 && s == 0) return mp(p, q);
    ll g = r * r + s * s;
    ll np = near(p * r + q * s, g), nq = near(q * r - p * s, g);
    ll a = p - (np * r - nq * s), b = q - (nq * r + np * s);
    return get(r, s, a, b);
};

#line 1 "cpp_src/number_theory/GaussGcd.cpp"
ll near(ll x, ll d) {
    bool p = x >= 0;
    x = abs(x);
    ll t = x % d * 2 >= d ? x / d + 1 : x / d;
    if (!p) t = -t;
    return t;
}

pair<ll, ll> get(ll p, ll q, ll r, ll s) {
    if (r == 0 && s == 0) return mp(p, q);
    ll g = r * r + s * s;
    ll np = near(p * r + q * s, g), nq = near(q * r - p * s, g);
    ll a = p - (np * r - nq * s), b = q - (nq * r + np * s);
    return get(r, s, a, b);
};