Cod sursa(job #234742)

Utilizator andumMorie Daniel Alexandru andum Data 21 decembrie 2008 21:16:29
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb

#include <stdio.h>  
int t;  
int euclid(int a,int b,int &x,int &y)  
{    
   if (b==0)   
   {    
      x=1;    
      y=0;  
      return a;    
   }  
   int x0,y0,d;    
   d=euclid(b,a%b,x0,y0);    
   x=y0;    
   y=x0-(a/b)*y0;      
   return d;      
}    
int main ()  
{  
    freopen ("euclid3.in","r",stdin);  
    freopen ("euclid3.out","w",stdout);      
    int i;  
    scanf ("%d",&t);  
    for (i=1; i<=t; ++i)  
    {  
        int a,b,c;          
        scanf ("%d%d%d",&a,&b,&c);  
        int d,x,y;  
        d=euclid(a,b,x,y);  
        if (c%d)  
            printf ("0 0\n");  
        else  
            printf("%d %d\n",x*(c/d),y*(c/d));  
    }  
    return 0;  
}