Cod sursa(job #2813004)

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

using namespace std;

ifstream in("euclid3.in");
ofstream out("euclid3.out");
	
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 - (a/b) * y;
	x = aux;
	return g;
	
}

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

int main() {

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