Cod sursa(job #2645897)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 29 august 2020 22:14:32
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <cstdio>

using namespace std;

void euclid(int a, int b, int &c, int &x, int &y) {
	if (b == 0) {
		c = a;
		x = 1;
		y = 0;
        return;
	}
	int x0, y0;
	euclid(b, a%b, c, x0, y0);

	x = y0;
	y =  x0 - (a/b) * y0;
}



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

	int n, a, b, c, d, x, y;

	scanf("%d", &n);

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

        if (x == 1 && y == 0)
            printf("0 0\n");
        else
            printf("%d %d\n", x * (d/c), y *(d/c));

	}

	return 0;
}