Pagini recente » Cod sursa (job #911260) | Cod sursa (job #1170572) | Cod sursa (job #3155241) | Cod sursa (job #2096636) | Cod sursa (job #2737444)
#include <stdio.h>
#include <utility>
using namespace std;
int gcd(int, int, pair <int, int> &);
int main() {
FILE *f = fopen("euclid3.in", "r");
FILE *g = fopen("euclid3.out", "w");
int T;
fscanf(f, "%d\n", &T);
while (T--) {
int x, y, t;
fscanf(f, "%d %d %d\n", &x, &y, &t);
pair <int, int> ans;
int cmmdc = gcd(x, y, ans);
if (t % cmmdc) {
fprintf(g, "0 0\n");
continue;
}
fprintf(g, "%d %d\n", ans.first * t / cmmdc, ans.second * t / cmmdc);
}
return 0;
}
int gcd(int a, int b, pair <int, int> & ans) {
int r = a % b;
pair <int, int> ares = {1, 0}, bres = {0, 1}, rres = {1, -(a / b)};
while (r) {
a = b;
ares = bres;
b = r;
bres = rres;
r = a % b;
rres = {ares.first - (a / b) * bres.first, ares.second - (a / b) * bres.second};
}
ans = bres;
return b;
}