Cod sursa(job #1069415)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 29 decembrie 2013 23:31:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 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;

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

    scanf ("%d", & t);

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

        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);
    }

    return 0;
}
*/
# include <cstdio>

int gcd (int a, int b, int & x, int & y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }

    int x0, y0, d;
    d = gcd (b, a % b, x0, y0);

    x = y0;
    y = x0 - (a / b) * y0;

    return d;
}

int main()
{
    freopen("euclid3.in", "rt", stdin);
    freopen("euclid3.out", "wt", stdout);

    int t, x, y, d;

    scanf ("%d", & t);
    while (t --)
    {
        int a, b, c;
        scanf ("%d %d %d", & a, & b, & c);

        d = gcd (a, b, x, y);

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

    return 0;
}