Cod sursa(job #841302)

Utilizator s4d1ckOrtan Seby s4d1ck Data 23 decembrie 2012 23:31:44
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
//cerinta: a * x + b * y = cmmdc(a, b)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

void euclid(int a, int b, int c, int *x, int *y)
{
	if (a == c)
	{
		*x = 1;
		*y = 0;
		return;
	}
	else if (b == c)
	{
		*x = 0;
		*y = 1;
		return;
	}
	
	vector<int> cat;
	int r, n;
	
	while (b != 0)
	{
		r = a % b;
		cat.push_back(a / b);
		a = b;
		b = r;
	}
	
	if (c % a != 0) 
	{
		*x = 0; *y = 0;
		return;
	}
	
	n = cat.size();
	n--;
	
	int xx = 1, yy = -cat[n-1];
	
	for (int i = n-2; i >=0; i--)
	{
		int t = yy;
		yy = xx - yy * cat[i];
		xx = t;
	}
	
	int d = c / a;
	*x = xx * d;
	*y = yy * d;
	

}

int main()
{
	int a, b, c, m;
	ifstream f("euclid3.in");
	ofstream g("euclid3.out");
	f>>m;
	int x, y;
	for (int i = 0; i<m; i++)
	{
		f>>a>>b>>c;
		euclid(a, b, c, &x, &y);
		g<<x<<" "<<y<<"\n";
	}
	f.close(); g.close();
	
	return 0;
}