Cod sursa(job #1235985)

Utilizator PatrikStepan Patrik Patrik Data 1 octombrie 2014 00:19:44
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
    #include<cstdio>
    using namespace std;
    int T , a, b , c ,x,y ,d;

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

    int main()
    {
        freopen("euclid3.in" , "r" , stdin );
        freopen("euclid3.out" , "w" , stdout );
        scanf("%d" , &T );
        for(int i = 1 ; i<= T ; ++i )
        {
            scanf("%d%d%d" , &a , &b , &c );
            euclid(a,b,x,y,d);
            if(c%d)
                printf("0 0\n");
            else
                printf("%d %d\n" , (c/d)*x , (c/d)*y);
        }
        return 0;
    }