Cod sursa(job #784456)

Utilizator AndupkIonescu Alexandru Andupk Data 5 septembrie 2012 20:37:57
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
using namespace std;
int euclid(int a , int b)
{
int c;
 while(b)
 {
  b=a%b;
  a=b;
  b=c;	 
 }
return a;
}

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

int main()
{
ifstream in("euclid3.in");
ofstream out("euclid3.out");
int a,b,c,d,t,x,y;
in>>t;
while(t)
{
in>>a>>b>>c;
d=euclid_extins(a,b,x,y);
if(c%d)
	 out<<"0 0"<<endl;
  else out<<x*(c/d)<<" "<<y*(c/d)<<endl;
t--;
}
return 0;
}