Cod sursa(job #1204160)

Utilizator alexsimi66FMI Simandi Alexandru alexsimi66 Data 2 iulie 2014 10:35:54
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<fstream>

using namespace std;

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

int main ()
{
	ifstream fin ("euclid3.in");
	ofstream fout ("euclid3.out");
	int n;
	fin >> n;
	int a, b, d;
	int x, y;
	for (int i = 0; i < n; i++)
	{
		fin >> a >> b >> d;
		int c = d;
		euclid (a, b, &d, &x, &y);
		if (c%d)
		{
			fout << "0 0\n";
		}
		else
		{
			fout << x*(c / d) << " " << y*(c / d) << "\n";
		}
	}
	return 0;
}