Cod sursa(job #1025882)

Utilizator danny794Dan Danaila danny794 Data 10 noiembrie 2013 18:31:28
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

int gcd(int a, int b){
	if (a == 0 || b == 0)
		return a + b;
	else if (a > b)
		return gcd(b, a % b);
	else
		return gcd(a, b % a);
}

pair<int, int> extended_euclid(int a, int b){
	pair<int, int> result;

	if (a == 1){
		result.first  = 1;
		result.second = 0;
	} else if (b == 1) {
		result.first  = 0;
		result.second = -1;
	} else {
		int d = a / b, c = a % b;
		pair<int, int> p = extended_euclid(b, c);
		result.second = - (p.second * d + p.first);
		result.first = - p.second;
	}
	return result;
}

void solve(int a, int b, int c){
	int cmmdc = gcd(abs(a), abs(b));
	if (c % cmmdc != 0){
		g << "0 0\n";
	} else {
		a = a / cmmdc;
		b = b / cmmdc;
		c = c / cmmdc;
		pair<int, int> result = extended_euclid(abs(a), abs(b));
		if (a != 0)
			result.first = a / abs(a) * result.first;
		if (b != 0)
			result.second = b / abs(b) * result.second;
		g << result.first * c << " " << - result.second * c << '\n';
	}
}

int main(){

	int T, a, b, c;
	f >> T;
	for (int i = 1; i <= T; i++){
		f >> a >> b >> c;
		solve(a, b, c);
	}
	f.close();
	g.close();
	return 0;
}