Cod sursa(job #785771)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 9 septembrie 2012 20:42:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
//Algoritmul extins al lui euclid https://infoarena.ro/algoritmul-lui-euclid
//(a,b)=a*x+b*y, unde x,y nr intregi si a,b nr naturale
//Cerinta: a*x+b*y=c. Se dau a, b, c. sa se det. x si y;
#include <fstream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
void gcdEx(int a,int b,int& d,int& x,int& y);
int main()
{
	int T,a,b,c,d,x,y;
	fin>>T;
	for (int i=0;i<T;i++)
	{
		fin>>a>>b>>c;
		gcdEx(a,b,d,x,y);
		if (c%d)						//daca numerele sunt prime intre ele nu exista solutii
			fout<<0<<' '<<0<<'\n';
		else
			fout<<c/d*x<<' '<<c/d*y<<'\n';
	}
	fin.close();
	fout.close();
	return 0;
}
void gcdEx(int a,int b,int& d,int& x,int& y)
{
	if (b==0)
	{
		d=a;
		x=1;
		y=0;
	}
	else
	{
		int x0,y0;
		gcdEx(b,a%b,d,x0,y0);
		x=y0;
		y=x0-(a/b)*y0;
	}
}