Cod sursa(job #143712)

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

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

long a,b,c,T;

void calc(long a,long b,long &d,long &x,long &y)
{
     if(b == 0)
     {
          x = 1;
          y = 0;
          d = a;
     }
     else
     {
         long 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);
        long 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;
}