Pagini recente » Cod sursa (job #732385) | Cod sursa (job #560639) | Cod sursa (job #258720) | Cod sursa (job #614549) | Cod sursa (job #2241766)
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <assert.h>
using LL = long long;
using ULL = int long long;
const std::string _problemName = "euclid3";
namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}
#define cin fin
#define cout fout
void euclid(int& d, int& x, int& y, int a, int b) {
if (b == 0) {
d = a;
x = 1;
y = 0;
return;
}
int x1, y1;
euclid(d, x1, y1, b, a % b);
// b * x1 + (a % b) * y1 == d
// a * x + b * y == d
// b * x1 + (a % b) * y1 == a * x + b * y
// b * (x1 - y) + (a - (a / b) * b) * y1 - a * x == 0
// b * (x1 - y) + a * y1 - b * y1 * (a / b) - a * x == 0
// b * (x1 - y - y1 * (a / b)) + a * (y1 - x) == 0
x = y1;
y = x1 - y1 * (a / b);
}
std::pair<int, int> solveEuclid(int a, int b, int c) {
int d, x, y;
euclid(d, x, y, a, b);
if (c % d != 0) {
return std::make_pair(0, 0);
}
x *= c / d;
y *= c / d;
return std::make_pair(x, y);
}
int main() {
int t;
std::cin >> t;
while (t--) {
int a, b, c;
std::cin >> a >> b >> c;
auto sol = solveEuclid(a, b, c);
std::cout << sol.first << ' ' << sol.second << '\n';
}
return 0;
}