Cod sursa(job #1458936)

Utilizator aciobanusebiCiobanu Sebastian aciobanusebi Data 8 iulie 2015 19:58:54
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<iostream>
#include<cmath>
#include<fstream>
using namespace std;

struct solutie
{
	int alfa, beta,cmmdc;
};

struct comb_lin
{
	int v[2];
	comb_lin(int x = 0, int y = 0)
	{
		v[0] = x;
		v[1] = y;
	}
	comb_lin operator-(comb_lin x)
	{
		comb_lin rezultat;
		rezultat.v[0] = v[0] - x.v[0];
		rezultat.v[1] = v[1] - x.v[1];
		return rezultat;
	}
	friend comb_lin operator*(int q, comb_lin x)
	{
		comb_lin rezultat;
		rezultat.v[0] = q*x.v[0];
		rezultat.v[1] = q*x.v[1];
		return rezultat;
	}
	int operator[](int i)
	{
		return v[i];
	}
};

solutie euclid_extins(int a, int b, int c)
{
	int r, q;
	comb_lin Va(1,0), Vb(0,1), Vr;
	bool sign_a=a<0, sign_b=b<0;
	a = abs(a);
	b = abs(b);
	while (b)
	{
		q = a / b;
		r = a%b;		Vr = Va - q*Vb;
		a = b;			Va = Vb;
		b = r;			Vb = Vr;
	}
	int cmmdc = a;
	
	solutie s;
	s.alfa = Va[0];
	s.beta = Va[1];
	if(sign_a)	s.alfa*=-1;
	if(sign_b)	s.beta*=-1;
	s.cmmdc = cmmdc;

	return s;
}

int main()
{
	unsigned T;
	ifstream f("euclid3.in");
	ofstream g("euclid3.out");
	f >> T; 
	for (unsigned i = 1; i <= T; ++i)
	{
		int a, b, c;
		f >> a >> b >> c;
		solutie s = euclid_extins(a, b, c);
		if (c%s.cmmdc==0)//are solutii
		{
			int q = c / s.cmmdc;
			s.alfa *= q;
			s.beta *= q;
			g << s.alfa << ' ' << s.beta << '\n';
		}
		else
		{
			g << 0 << ' ' << 0 << '\n';
		}
	}
	f.close();
	g.close();
	return 0;
}