Cod sursa(job #1112092)

Utilizator fhandreiAndrei Hareza fhandrei Data 19 februarie 2014 13:32:25
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
// Include
#include <fstream>
using namespace std;

// Functii
void euclid(int a, int b, int *div, int *x, int *y);

// Variabile
ifstream in("euclid3.in");
ofstream out("euclid3.out");

int equations;

// Main
int main()
{
	in >> equations;
	
	int a, b, c;
	while(equations--)
	{
		in >> a >> b >> c;
		int x, y, div;
		euclid(a, b, &div, &x, &y);
		if(c % div)
			x = y = 0;
		out << x*(c/div) << ' ' << y*(c/div) << '\n';
	}
	
	in.close();
	out.close();
	return 0;
}

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