Cod sursa(job #1834757)

Utilizator rockerboyHutter Vince rockerboy Data 25 decembrie 2016 01:04:42
Problema Heapuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <tuple>

std::ifstream in ("euclid3.in");
std::ofstream out("euclid3.out");

struct result
{
    int gcd, x, y;
};

result eucl_extended (int a, int b)
{
    if (b == 0) return {a, 1, 0};

    int r, q, x0, y0, x1, y1, tx, ty;
    x0 = 1; y0 = 0;
    x1 = 0; y1 = 1;

    while (1)
    {
        r = a % b;
        q = a / b;
        if (r == 0) break;
        tx = x1;
        ty = y1;
        x1 = x0 - q*x1;
        y1 = y0 - q*y1;
        x0 = tx;
        y0 = ty;
        a = b;
        b = r;
    }

    return {b, x1, y1};
}

int main()
{
    int t, a, b, c;
    result res;

    in >> t;
    for (int i=0; i<t; i++)
    {
        in >> a >> b >> c;
        res = eucl_extended(a, b);
        if (c % res.gcd)
        {
            out << "0 0\n";
        }
        else
        {
            out << res.x *c/res.gcd << " " << res.y *c/res.gcd << "\n";
        }
    }
}