Cod sursa(job #1774303)

Utilizator RobertSSamoilescu Robert RobertS Data 8 octombrie 2016 19:45:35
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>

using namespace std;


int gcd(int a, int b){


	while (b) {
		int c = a % b;
		a = b;
		b = c;
	}

	return a;
}

void euclid(int &a, int &b, int &x, int &y) {
	if (b == 0) {
		x = 1;
		y = 0;
	} else {
		int x0, y0, c;
		c = a % b;
		euclid(b, c, x0, y0);
		x = y0;
		y = x0 - (a / b) * y0;
	}
}


int main() {

	ifstream fin("euclid3.in");
	ofstream fout("euclid3.out");

	int T; 
	fin >> T;

	for (int i = 0; i < T; i++) {
		int a, b, c;
		fin >> a >> b >> c;

		int comm_div = gcd(a, b);
		if (c % comm_div) {
			fout << "0 0\n";
		} else {
			int x, y;
			euclid(a, b, x, y);

			int q = c / comm_div;
			fout << x * q << " " << y * q << '\n';
		}


	}


	fin.close();
	fout.close();

	return 0;
}