Cod sursa(job #1892622)

Utilizator Tyler_BMNIon Robert Gabriel Tyler_BMN Data 25 februarie 2017 10:17:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <fstream>

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

int T,a,b,c;

pair<int,int> euclidExt(int x,int y)
{
    if(y==0)
        return {1,0};
    pair<int,int> p = euclidExt(y,x%y);
    return {p.second, p.first-(x/y)*p.second};
}

int main()
{
    fin>>T;
    for(;T;T--)
    {
        fin>>a>>b>>c;
        pair<int,int> rez = euclidExt(a,b);
        int d=rez.first*a+rez.second*b;
        if(c%d!=0)
            fout<<"0 0";
        else
            fout<<rez.first*(c/d)<<" "<<rez.second*(c/d);
        fout<<"\n";
    }
    return 0;
}