Cod sursa(job #543672)

Utilizator algoritmarOvidiu Andrei algoritmar Data 28 februarie 2011 14:22:18
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <iostream>
//#include <assert>
using namespace std;
#define FIN "euclid3.in" 
#define FOUT "euclid3.out" 
#define L 4000000001
#define N_M 1e9
#define ll long long
//#define ASSERT(x<y)  if(x<y) return 1; else cout << "assert failed \n";
ifstream fin(FIN); 
ofstream fout(FOUT); 

int rem(int x, int y)
{
   return x - (x/y) * y;
}
int x,y;
//int exteded_gcd(int a,int b)
int ext_gcd(int a,int b,int &x, int &y)
{
    //int z;
    if(b == 0)
    {
	x = 0, y = 1;
    	return a;	
    }
   
    int x0, y0, d;
    d = ext_gcd(b,a%b,x0,y0);
    x = y0;
    y = x0 -(a/b) * y0;
    return d;
    /*
    if(y == 0) { 
    	cout << " x = " << x << endl;
	return x;
    }
    else if (x == 0){ 
	    cout << " y = " << y << endl;
	    return y;
    	} else { cout << " z = " << z << endl;
		 z = rem(x,y);
   	return extended_gcd(y,z);
    }
    */
    /*
    if(a%b == 0)
    {
	x = 0, y = 1;
    	return b;	
    }
    //y = y;
    x = x-(y*(a/b));
    return extended_gcd(b,a%b);*/
}
int main()
{
   int n,d;
   ll a,b,c;

   fin >> n; 
   //r(int i = 0,ASSERT(n <= 100); n; ++i){
   for(int i = 0; i< n; ++i){
      fin >> a >> b >> c;
      //cout << a << " " << b << " " << c << "\n";
      //x = y = 1;
      d = ext_gcd(a,b,x,y);
      if(c%d)
      {
	 x = y = 0;
	 fout << x << " " << y << "\n";
      }
      else
       fout << x * (c/d) << " " << y * (c/d) << "\n";  
	
   }      

   return 0;
}