Cod sursa(job #2214724)

Utilizator bcrsqCont Sters bcrsq Data 19 iunie 2018 21:01:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <cstdio>

using namespace std;

void euclid_extins(int a, int b, int &x, int &y, int &d);

int main() {
	int a, b, c;
	int t;

	freopen("euclid3.in", "r", stdin);
	freopen("euclid3.out", "w", stdout);

	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		scanf("%d %d %d", &a, &b, &c);
		int x, y, d;

		euclid_extins(a, b, x, y, d);

		if (c % d) {
			printf("0 0\n");
		} else {
			printf("%d %d\n", x * (c / d), y * (c / d));
		}
	}


	return 0;
}

void euclid_extins(int a, int b, int &x, int &y, int &d) {
	if (b == 0) {
		d = a;
		x = 1;
		y = 0;
	} else {
		int x0, y0;
		euclid_extins(b, a % b, x0, y0, d);
		x = y0;
		y = x0 - (a / b) * y0;
	}
}