Cod sursa(job #3356729)

Utilizator Car13Carmi Carabas Car13 Data 3 iunie 2026 18:28:44
Problema Algoritmul lui Euclid extins Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>

using namespace std;

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

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

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

    while (b != 0) {
        long long q = a / b;
        long long r = a % b;

        a = b;
        b = r;

        long long x_nou = x0 - q * x1;
        long long y_nou = y0 - q * y1;

        x0 = x1;
        x1 = x_nou;

        y0 = y1;
        y1 = y_nou;
    }

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

int main() {

    int T;
    long long a, b, c;
    long long x = 0, y = 0;
    long long d;
    fin >> T;

    for(int i = 1; i <= T; i ++) {
        x = 0; y = 0;
        fin >> a >> b >> c;
        d = euclid_ext(abs(a), abs(b), x, y);

        if (c % d == 0) {
            x = x * (c / d);
            y = y * (c / d);
            if (a < 0) {
                x = -x;
            }
            if (b < 0) {
                y = -y;
            }
            fout << x << " " << y << "\n";
        } 
        else {
            fout << 0 << " " << 0;
        }
    }

    return 0;
}