Cod sursa(job #2812994)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 5 decembrie 2021 16:45:31
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.51 kb
#include <bits/stdc++.h>

using namespace std;

int extended_euclid(int a,int b,int &x,int &y) {
	if(b == 0) {
		x = 1, y = 0;
		return a;
	}
	int g = extended_euclid(b, a%b, x, y);
	int aux = y;
	y = x - (b * (a/b) ) * y;
	x = aux;
	return g;
	
}

void test_case() {
	int a, b, c;
	cin >> a >> b >> c;
	int x, y;
	int g = extended_euclid(a, b, x, y);
	if( c % g > 0 ) cout << "0 0\n";
	else {
		cout << x * c/g << ' ' << y * c/g << '\n';
	}
	
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		test_case();
	}
	return 0;
}