Cod sursa(job #1401268)

Utilizator alexandru70Ungurianu Alexandru alexandru70 Data 25 martie 2015 19:00:16
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <iostream>
#include <cmath>

using namespace std;

struct EuclidResult {
	int x,y,gcd;
};

EuclidResult euclid(int a, int b) {
	if(b==0) {
		return {1,0,a};
	}
	else {
		EuclidResult last = euclid(b,a%b);
		return {last.y,last.x-(a/b)*last.y,last.gcd};
	}
}

int main() {
	ifstream in("euclid3.in");
	ofstream out("euclid3.out");

	unsigned t;
	in >> t;
	for(unsigned i = 0; i < t; ++i) {
		int a,b,c;
		in >> a >> b >> c;
		EuclidResult res = euclid(a,b);
		if((c*1.0f)/res.gcd != c/res.gcd) {
			out << "0 0\n";
		}
		else {
			int rap = c/res.gcd;

			out << res.x*rap << ' ' << res.y*rap << '\n';
		}
	}
	return 0;
}