Cod sursa(job #143711)

Utilizator DorinOltean Dorin Dorin Data 26 februarie 2008 20:06:11
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
# include <stdio.h>

# define input "euclid3.in"
# define output "euclid3.out"

int a,b,c,T;

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

int main()
{
    freopen(input, "r", stdin);
    freopen(output, "w",stdout);
    
    scanf("%d",&T);
    
    while(T)
    {
    
        scanf("%d%d%d",&a,&b,&c);
        int x,y,d;
        calc(a,b,d,x,y);
        if(c%d != 0)
               printf("0 0\n");
        else
            printf("%d %d\n",x*c/d,y*c/d);
        T--;
    }
    
    return 0;
}