Cod sursa(job #463821)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 17 iunie 2010 16:14:21
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>

#define file_in "euclid3.in"
#define file_out "euclid3.out"

int Q,a,b,c;

void citire()
{
    freopen(file_in,"r,"stdin);
    freopen(file_out,"w",stdout);

    scanf("%d", &Q);
}

int euclid(int a, int b, int &x, int &y)
{
    if (b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int x0,y0,d;
    d=euclid(b,a%b,x0,y0);
    x=y0;
    y=x0-(a/b)*y0;
    return d;
}

void solve()
{
    while(Q--)
    {
        scanf("%d %d %d", &a, &b, &c);
        int d,x,y;
        d=euclid(a,b,x,y);
        if (c%d)
        printf("0 0\n");
        else
        printf("%d %d\n", x*(c/d),y*(c/d));
    }
}

int main()
{
    citire();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}