Pagini recente » Statistici Oleg Ratsa (pakapu) | Cod sursa (job #1907838) | Monitorul de evaluare | Cod sursa (job #1850529) | Cod sursa (job #2195468)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
void executeExtendedEuclideanAlgorithm(int a, int b, int &x, int &y, int &gcd) {
int x1 = 1, y1 = 0;
int x2 = 0, y2 = 1;
int xAux, yAux;
int r, q;
while (a % b != 0) {
q = a / b;
r = a % b;
xAux = x2;
yAux = y2;
x2 = x1 - q * x2;
y2 = y1 - q * y2;
x1 = xAux;
y1 = yAux;
a = b;
b = r;
}
gcd = b;
x = x2;
y = y2;
}
int main() {
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
int T, a, b, c;
int x, y, gcd;
fin >> T;
while (T--) {
fin >> a >> b >> c;
executeExtendedEuclideanAlgorithm(a, b, x, y, gcd);
if (c % gcd == 0) {
fout << (c / gcd) * x << ' ' << (c / gcd) * y << '\n';
}
else {
fout << 0 << ' ' << 0 << '\n';
}
}
return 0;
}