Cod sursa(job #3208065)

Utilizator DajaMihaiDaja Mihai DajaMihai Data 27 februarie 2024 17:17:00
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <bits/stdc++.h>

using namespace std;

#define int long long

#ifndef LOCAL
ifstream in("euclid3.in");
ofstream out("euclid3.out");
#define cin in
#define cout out
#endif

pair<int, int> euclid3(int a, int b) {
    // ax + by = g
    if(a < 0) {
        pair<int, int> xy = euclid3(-a, b); // (-a)x + by = g
        int x = xy.first, y = xy.second;
        // a (-x) + by = g
        return {-x, y};
    }
    if(b < 0) {
        pair<int, int> xy = euclid3(a, -b); // ax + (-b)y = g
        int x = xy.first, y = xy.second;
        // ax + (-y)b = g
        return {x, -y};
    }

    if(b == 0) return {1, 0};
    if(a == 0) return {0, 1};

    if(a > b) {
        pair<int, int> yx = euclid3(b, a);
        int y = yx.first, x = yx.second;
        return {x, y};
    }

    // Cazul mai greu
    int k = b / a;
    pair<int, int> xpyp = euclid3(a, b - k * a);
    int xp = xpyp.first;
    int yp = xpyp.second;

    int y = yp;
    int x = xp - k * yp;
    return {x, y};
}

void solve() {
    int a, b, c; cin >> a >> b >> c;
    int g = __gcd(a, b);

    if(c % g != 0) {
        cout << "0 0" << '\n';
        return;
    }

    int d = c / g;
    pair<int, int> xy = euclid3(a, b);
    int x = xy.first, y = xy.second;
    x *= d; y *= d;

    if(a*x + b*y == -c) {
        x = -x; y = -y;
    }

    const int limita = 2e9;

    if(x > limita) {
        // trebuie sa gasesc k a.i. x - k * b < limita
        // x < k * b + limita
        // k > (x - limita) / b

        int k = (x - limita) / b + 1;
        x -= k * b;
        y += k * a;
    }

    if(y > limita) {
        int k = (y - limita) / a + 1;
        y -= k * a;
        x += k * b;
    }

    if(x < -limita) {
        int k = (-x - limita) / b + 1;
        x += k * b;
        y -= k * a;
    }

    if(y < -limita) {
        int k = (-y - limita) / a + 1;
        y += k * a;
        x -= k * b;
    }

    cout << x << ' ' << y << '\n';
}

int32_t main() {
    int t; cin >> t;
    while(t--) solve();
}