Cod sursa(job #256441)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 11 februarie 2009 19:09:55
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream.h>
#include <iostream.h>

#define IN "euclid3.in"
#define OUT "euclid3.out"

ifstream fin(IN);
ofstream fout(OUT);

int teste;
int a,b,c;
int x,y,d;
 
inline int gcd(int a,int b,int &x,int &y); 
 
int main()
{
 fin>>teste;
 
 while(teste)
 {
  teste--;
  
  fin>>a>>b>>c;

  d = gcd(a,b,x,y);
		
  if (c % d)
   fout<<"0"<<" "<<"0"<<endl;
  else
   fout<<x*(c/d)<<" "<<y*(c/d)<<endl;
 }

return 0;
}

inline int gcd(int a,int b,int &x,int &y)
{
 if (b==0)
 {
  x=1;
  y=0;
  return a;
 }

 int x0,y0,D;
 D = gcd(b,a%b,x0,y0);
	
 x=y0;
 y=x0-(a/b)*y0;
 
 return D;	
}