Cod sursa(job #3311513)

Utilizator EduardoDinutaDinuta Eduard Stefan EduardoDinuta Data 22 septembrie 2025 20:34:09
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>

std::ifstream in("euclid3.in");
std::ofstream out("euclid3.out");

int gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x0, y0;
    int ans = gcd(b, a % b, x0, y0);
    
    x = y0;
    y = x0 - (a / b) * y0;

    return ans;
}

void solve() {
    int a, b, c;
    in >> a >> b >> c;

    int x, y;
    int d = gcd(a, b, x, y);

    if (c % d != 0) {
        out << 0 << " " << 0 << '\n';
    } else {
        out << x * c / d << " " << y * c / d << '\n';
    }
}

int main() {
    int t;

    in >> t;
    while (t--) {
        solve();
    }


    return 0;
}