Cod sursa(job #2784284)

Utilizator Robert.BrindeaBrindea Robert Robert.Brindea Data 16 octombrie 2021 11:26:26
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <tuple>

using namespace std;

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

tuple<long long, long long, long long> euclid(long long x, long long y)
{
    if(y == 0) return make_tuple(x, 1, 0);

    auto p = euclid(y, x%y);
    return make_tuple(get<0>(p), get<1>(p), get<1>(p) - get<2>(p)*(x/y));
}

int main()
{
    int t;
    fin >> t;
    for(int i = 0; i < t; i++)
    {
        long long a, b, c;
        fin >> a >> b >> c;
        auto p = euclid(a, b);
        int d = get<0>(p), x = get<1>(p), y = get<2>(p);
        if(c%d != 0) fout << "0 0\n";
        else
            fout << x * c/d << " " << y * c/d << "\n";
    }
    return 0;
}