Cod sursa(job #2668229)

Utilizator marquiswarrenMajor Marquis Warren marquiswarren Data 4 noiembrie 2020 17:49:02
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>

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

	int t;
	scanf("%d", &t);

	while (t--) {
		int mat[2][3]{}, a, b, c;

		scanf("%d %d %d", &a, &b, &c);
		mat[0][0] = a;
		mat[1][0] = b;
		mat[0][1] = mat[1][2] = 1;


		while (mat[0][0] * mat[1][0]) {
			int r = mat[0][0] < mat[1][0];
			int c = mat[r][0] / mat[!r][0];
			for (int j = 0; j < 3; j++)
				mat[r][j] -= c * mat[!r][j];
		}

		int r = mat[0][0] < mat[1][0];
		int gcd = mat[r][0];

		if (c % gcd != 0)
			printf("0 0\n");
		else {
			c /= gcd;
			printf("%d %d\n", mat[r][1] * c, mat[r][2] * c);
		}
	}

	return 0;
}