Cod sursa(job #3233445)

Utilizator Bogdan_128Pandele Bogdan Bogdan_128 Data 3 iunie 2024 14:12:44
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
//#include <iostream>
#include <fstream>

using namespace std;

ifstream cin("euclid3.in");
ofstream cout("euclid3.out");


long long gcd_ext(long long A, long long B, long long* X, long long* Y) {
    if (A == 0) {
        *X = 0;
        *Y = 1;
        return B;
    }

    long long X1, Y1;
    long long gcd = gcd_ext(B % A, A, &X1, &Y1);

    *X = Y1 - (B / A) * X1;
    *Y = X1;

    return gcd;
}


bool solve_ec(long long a, long long b, long long c, long long* x, long long* y) {
    long long X = 0, Y;
    long long gcd = gcd_ext(a, b, &X, &Y);


    if (c % gcd != 0) {
        return false;
    }

    *x = X * (c / gcd);
    *y = Y * (c / gcd);

    return true;
}

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

    for (int i = 0; i < T; i++) {
        long long a, b, c;
        cin >> a >> b >> c;
        long long x = 0, y;
        if (solve_ec(a, b, c, &x, &y)) {
            cout << x << " " << y << '\n';
        }
        else {
            cout << "0 0" << '\n';
        }
    }
    return 0;
}