Cod sursa(job #418713)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 16 martie 2010 12:00:39
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<string>

using namespace std;

void cmmdc(int a,int b,int &d,int &x,int &y)
{
     if(!b)
     {
          x=1,y=0;
          d=a;
          return ; 
     }
     
     int na=b,nb=a%b;
     
     cmmdc(na,nb,d,x,y);
     
     int nx=y,ny=x-(a/b)*y;
     
     x=nx,y=ny;
}

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