Cod sursa(job #1129620)

Utilizator PatrikStepan Patrik Patrik Data 28 februarie 2014 00:07:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
    #include<cstdio>
    using namespace std;
    int T , x , y , c,d;

    void euclid(int a , int b , int &x , int &y  , int &d);

    int main()
    {
        int a , b;
        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;
    }

    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);
            y = x0 - a/b*y0;
            x = y0;
        }
    }