Pagini recente » Cod sursa (job #584011) | Cod sursa (job #451457) | Cod sursa (job #3038595) | Cod sursa (job #2388590) | Cod sursa (job #2756647)
#include <fstream>
using namespace std;
void extendedEuclid(long long A, long long B, long long &X, long long &Y, long long &D)
{ // A*X + B*Y = D
if (!B) {
D = A;
X = 1;
Y = 0;
return;
}
long long _X, _Y;
extendedEuclid(B, A % B, _X, _Y, D);
// B * _X + (A - [A/B]*B) * _Y = D
X = _Y;
Y = _X - A/B * _Y;
}
int main()
{
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
fin.sync_with_stdio(false);
fin.tie(0);
int N;
fin >> N;
for (int i = 0; i < N; ++i) {
long long A, B, C, X, Y, D;
fin >> A >> B >> C;
extendedEuclid(A, B, X, Y, D);
// A*X + B*Y = D and we want A*X' + B*Y' = C
if (C % D != 0)
fout << "0 0\n";
else
fout << X * (C/D) << " " << Y * (C/D) << "\n";
}
return 0;
}