Cod sursa(job #516586)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 24 decembrie 2010 21:44:14
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>

using namespace std;

struct trip
{
    int x, y, d;
};

trip euclid(int a, int b, trip w)
{
    if(b == 0)
    {
        w.x = 1;
        w.y = 0;
        w.d = a;
        return w;
    }
    else
    {
        w = euclid(b, a % b, w);
        int aux = w.y;
        w.y = w.x - (a / b) * w.y;
        w.x = aux;
    }
    return w;
}

int main()
{
    int a, b, c, cate;
    trip n;
    freopen ("euclid3.in","r",stdin);
    freopen ("euclid3.out","w",stdout);
    scanf("%d",&cate);
    while(cate--)
    {
        scanf("%d %d %d",&a,&b,&c);
        n = euclid(a,b,n);
        if(c % n.d == 0)
            printf("%d %d\n",n.x * (c / n.d),n.y * (c / n.d));
        else printf("0 0\n");
    }
    return 0;
}