Cod sursa(job #3350646)

Utilizator Alex_at_gameIustin-Alexandru Frateanu Alex_at_game Data 11 aprilie 2026 15:45:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(v) begin(v), end(v)
#define al(v, l, r) begin(v) + l, begin(v) + r + 1
#define sz(v) (int)v.size()
#define pb push_back
#define pob pop_back
#define fs first
#define sd second

constexpr int inf = 2e9;
constexpr ll infll = 4e18;

int gcd_extins(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x0, y0, g = gcd_extins(b, a % b, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
    return g;
}

void solve() {
    int a, b, c, x, y;
    cin >> a >> b >> c;
    int g = gcd_extins(a, b, x, y);

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

    cout << 1ll * x * (c / g) << " " << 1ll * y * (c / g) << "\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);

    int t = 1;
    cin >> t;

    do {
        solve();
    } while (--t);
}