Cod sursa(job #2904898)

Utilizator disinfoion ion disinfo Data 18 mai 2022 15:00:19
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <iostream>
#define LL int
using namespace std;

pair<LL,LL> bezout(LL a, LL b){
	pair<LL,LL> ans;
	int swapped = 0, minusa = 1, minusb = 1;
	LL q, r;

	if(a < 0){
		a = -a;
		minusa = -1;
	}

	if(b < 0){
		b = -b;
		minusb = -1;
	}

	if(a < b){
		swap(a, b);
		swapped = 1;
	}
	

	if(b == 0){
		ans = {1, 0};
	}
	else{
		q = a / b;
		r = a % b;
		pair<LL,LL> MN = bezout(b, r);
		ans = {minusa * MN.second, minusb * (MN.first - q * MN.second)};
	}

	if(swapped)
		swap(ans.first, ans.second);

	return ans;
}

int main(){
	ifstream fin;
	ofstream fout;
	fin.open("euclid3.in");
	fout.open("euclid3.out"); 
	LL a, b, c, n, d, x, y;
	pair<LL,LL> bez;
	fin >> n;

	for(int i = 1; i <= n; ++i){
		fin >> a >> b >> c;
		bez = bezout(a, b);
		x = bez.first, y = bez.second;
		d = a*x + b*y;
		if(c % d)
			fout << "0 0\n";
		else
			fout << x*(c / d) << " " << y*(c / d) << "\n";

	}
}