Cod sursa(job #1004545)

Utilizator ion824Ion Ureche ion824 Data 2 octombrie 2013 23:12:43
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<algorithm>
using namespace std;

int euclid(int a,int b,int &x,int &y)
{
   if(b==0)
     {
       x = 1;
       y = 0;
       return a;
     }  
   else
   {
       int x0,y0;
       int D = euclid(b,a%b,x0,y0);
       x = y0;
       y = x0 - (a / b) * y0;  
       return D;
   }
}

int main(){
    ifstream cin("euclid3.in");
    ofstream cout("euclid3.out");
   int A,B,C,T,X,Y,V;
    
    cin>>T;
    
    for(int i=1;i<=T;++i)
    {
      cin>>A>>B>>C;
      V = euclid(A,B,X,Y);
      
      if(C % V) cout<<"0 0\n";
        else cout<<(X * (C / V))<<' '<<(Y * (C / V))<<'\n';                    
    }
    
 return 0;   
}