Cod sursa(job #1892612)

Utilizator contnouAndrei Pavel contnou Data 25 februarie 2017 10:10:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>

using namespace std;

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

void readTestCase(int &a, int &b, int &c) {
	//
	f >> a >> b >> c;

	return;
}

void computeFactors(int a, int b, int &gcd, int &x, int &y) {
	//
	if (b == 0) {
		gcd = a;
		x = 1;
		y = 0;
	}
	else {
		computeFactors(b, a % b, gcd, x, y);
		int aux = x;
		x = y;
		y = aux - (a / b) * y;
	}
}
void solveTestCase(int a, int b, int c, int &x, int &y) {
	//
	int gcd;

	computeFactors(a, b, gcd, x, y);

	if (c % gcd != 0) {
		x = y = 0;
		return;
	}
	else {
		int multiplier = c / gcd;
		x = x * multiplier;
		y = y * multiplier;
	}


	return;
}

int main() {
	//
	int tc;
	int a, b, c, x = 0, y = 0;
	 
	f >> tc;
	while (tc) {
		//
		readTestCase(a, b, c);
		solveTestCase(a, b, c, x, y);
		g << x << " " << y << "\n";
		tc--;
	}

	return 0;
}