Cod sursa(job #2407830)

Utilizator FnZbZVrinceanu Radu FnZbZ Data 17 aprilie 2019 11:53:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>
using namespace std;

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

int t, M[100][4];
//vector < equation > v;

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

int main()
{
    cin>>t;
    for(int i = 0; i < t; i++) {
        cin>>M[i][0]>>M[i][1]>>M[i][2];

        int x, y;
        M[i][3] = getGCD(M[i][0], M[i][1], x, y);

        if(M[i][2] % M[i][3]) cout<<"0 0\n";
        else cout<<x*(M[i][2]/M[i][3])<<' '<<y*(M[i][2]/M[i][3])<<'\n';
    }
    cin.close();
    cout.close();
    return 0;
}