Cod sursa(job #2668729)

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

using LL = long long;

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

	LL 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);

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

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

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