Cod sursa(job #2813012)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 5 decembrie 2021 17:04:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <bits/stdc++.h>
#define ll long long 

using namespace std;

ifstream in("euclid3.in");
ofstream out("euclid3.out");
	
int extended_euclid(int a,int b,ll &x,ll &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;
	ll 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;
}