Pagini recente » Cod sursa (job #2852058) | Cod sursa (job #1320935) | Cod sursa (job #1137757) | Cod sursa (job #983913) | Cod sursa (job #543675)
Cod sursa(job #543675)
#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 = 1, y = 0;
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;
}