Cod sursa(job #3362243)

Utilizator DodeucGagiu Daniel Dodeuc Data 4 august 2026 18:04:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

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

    long long x1, y1;
    long long d = gcd_recursiv(b, a%b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return d;
}

long long gcd_iterativ(long long a, long long b, long long& x, long long& y){
    long long x0 = 1, x1 = 0;
    long long y0 = 0, y1 = 1;
    long long r0 = a, r1 = b;


    while (r1 != 0){
        long long q = r0 / r1;
        
        long long r_next = r0 - q * r1;
        r0 = r1;
        r1 = r_next;

        long long x_next = x0 - q * x1;
        x0 = x1;
        x1 = x_next;

        long long y_next = y0 - q * y1;
        y0 = y1;
        y1 = y_next;
    }

    x = x0;
    y = y0;
    return r0;
}

int main(){
    int T;
    fin >> T;

    for(int i = 1; i <= T; i++){
        long long a, b, c;
        
        fin >> a >> b >> c;

        long long x, y;
        long long d = gcd_recursiv(a, b, x, y);

        if(c % d != 0) fout << "0 0" << endl;
        else {
            fout << x * (c / d) << " " << y * (c / d) << endl;
        }
    }
}