Cod sursa(job #2904896)

Utilizator disinfoion ion disinfo Data 18 mai 2022 14:51:02
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <iostream>
#define LL int
using namespace std;

pair<LL,LL> bezout(LL a, LL b){
	pair<LL,LL> ans;
	bool swapped = 0;
	LL q, r;

	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 = {MN.second, 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";

	}
}