Cod sursa(job #227541)

Utilizator mika17Mihai Alex Ionescu mika17 Data 4 decembrie 2008 20:58:52
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
int C;
int main()
{
        int T,a,b,c,X[25],Y[25],R[25];

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

        scanf("%d",&T);

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

                if(a<b) { int aux = a; a = b; b = aux; }

                R[0] = a; R[1] = b;
                X[0] = 1; Y[0] = 0;
                X[1] = 0; Y[1] = 1;

                int i;
                for(i = 2; ;)
                {
                        C = R[i-2] / R[i-1];
                        R[i] = R[i-2] - C * R[i-1];
                        X[i] = X[i-2] - C * X[i-1];
                        Y[i] = Y[i-2] - C * Y[i-1];
                        if(R[i]) ++i;
                         else break;
                }
                --i;

                if(c % R[i] == 0)
                  printf("%d %d\n",X[i] * (c/R[i]),Y[i] * (c/R[i]));
                 else printf("0 0\n");
        }

        return 0;
}