Cod sursa(job #2668725)

Utilizator marquiswarrenMajor Marquis Warren marquiswarren Data 5 noiembrie 2020 11:26:49
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.51 kb
#include <bits/stdc++.h>

void euclid(int a, int b, int& d , int& x, int & y) {
	if (!b) {
		d = a;
		x = 1;
		y = 0;
		return;
	}

	int xp, yp;
	euclid(b, a % b, d, xp, yp);
	x = yp;
	y = xp - (a / b) * yp;
}

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

	int t, a, b, c, d, x ,y;
	scanf("%d", &t);

	while (t--) {
		scanf("%d %d %d", &a, &b, &c);	
		euclid(a, b, d, x, y);
		
		if (c % d != 0) {
			printf("0 0\n");
			continue;
		}

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