Cod sursa(job #2910650)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 23 iunie 2022 12:08:24
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

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

int euclid(int a, int b, int &x, int &y){
    //printf("euclid(%d, %d, %d, %d)\n", a, b, x, y);

    if(a == 0){
        x = 0;
        y = 1;
        return b;
    }

    int x1, y1;
    int d = euclid(b % a, a, x1, y1);

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

    return d;
}

void doTest(){
    int a, b, c;
    fin >> a >> b >> c;

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

    long long rez = 1LL * a * x * (c / d) + 1LL * b * y * (c / d);
    if(rez != c){
        fout << 0 << ' ' << 0 << "\n";
        return;
    }
    fout << x * (c / d) << ' ' << y * (c / d) << "\n";

}

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

    for(int q = 1; q <= nrTeste; q++){
        doTest();
    }

    return 0;
}