Cod sursa(job #477810)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 16 august 2010 13:29:12
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream>
#include<iostream>
using namespace std;

typedef long long int64;
int64 EuclidExt(int64 a, int64 b, int64 &x, int64 &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	else
	{
		int64 xi,yi;
		int64 cmmdc=EuclidExt(b, a%b, xi, yi);
		x=yi;
		y=xi-(a/b)*x;
		return cmmdc;
	}
}

int main()
{
	fstream fin("euclid3.in",fstream::in);
	fstream fout("euclid3.out",fstream::out);
	int T;
	fin>>T;
	for(int i=0; i<T; i++)
	{
		int64 x,y,a,b,c,d;
		fin>>a>>b>>c;
		d=EuclidExt(a,b,x,y);
		if(c%d!=0)
		{
			x=y=0;
		}
		fout<<x*(c/d)<<" "<<y*(c/d)<<"\n";
	}
	
	fin.close();
	fout.close();
	return 0;
}