Pagini recente » Cod sursa (job #1781685) | Cod sursa (job #688031) | Cod sursa (job #445636) | Cod sursa (job #889409) | Cod sursa (job #2690129)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
int t, a, b, d;
template<class T>
void __euclid(T a, T b, T &x, T &y) {
T y0, x0;
if (b == 0) {
x = 1;
y = 0;
return;
}
__euclid(b, a % b, x0, y0);
x = y0;
y = x0 - (a / b) * y0;
}
template<class T>
pair<T, T> extended_euclid(T a, T b, T d) {
if (d % __gcd(a, b) != 0) {
return make_pair(0, 0);
}
T x, y;
__euclid(a, b, x, y);
return make_pair((d / __gcd(a, b)) * x, (d / __gcd(a, b)) * y);
}
int main() {
fin >> t;
while (t --) {
fin >> a >> b >> d;
pair<int, int> ans = extended_euclid(a, b, d);
fout << ans.first << " " << ans.second << "\n";
}
return 0;
}