Cod sursa(job #1069385)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 29 decembrie 2013 22:20:14
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
# include <cstdio>

struct Euclid
{
    int x, y;
};

int c1, c2;

int euclidToInt (Euclid e)
{
    return e. x * c1 + e. y * c2;
}

Euclid getEuclid (int a, int b)
{
    Euclid e;

    e. x = a;
    e. y = b;

    return e;
}

Euclid getEuclid (Euclid a, Euclid b)
{
    int eTIA = euclidToInt (a), eTIB = euclidToInt (b);

    if (eTIA == 0)
        return b;

    if (eTIB == 0)
        return a;

    if (eTIA > eTIB)
    {
        a. y -= (eTIA / eTIB) * b. y;
        a. x -= (eTIA / eTIB) * b. x;

        return getEuclid (a, b);
    }

    else
    {
        b. y -= (eTIB / eTIA) * a. y;
        b. x -= (eTIB / eTIA) * a. x;

        return getEuclid (a, b);
    }
}

int main ()
{
    Euclid e;
    int t, c, cMMDC;
    bool f = false;

    freopen ("euclid3.in", "r", stdin);
    freopen ("euclid3.out", "w", stdout);

    scanf ("%d", & t);

    while (t --)
    {
        scanf ("%d %d %d", & c1, & c2, & c);

        f = false;

        e = getEuclid (getEuclid (1, 0), getEuclid (0, 1));

        cMMDC = euclidToInt (e);

        if (c % cMMDC)
            printf ("0 0\n");
        else
            printf ("%d %d\n", c * e. x / cMMDC, c * e. y / cMMDC);
    }
}