Cod sursa(job #818984)

Utilizator SilviussMezei Silviu Silviuss Data 18 noiembrie 2012 13:39:32
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>

using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int euclid (int a, int b)
{
	if(a<0)
		a=-a;
	if(b<0)
		b=-b;
	while(a && b)
	{
		if(a>b)
			a=a%b;
		else
			b=b%a;
	}
	return max(a,b);
}

int main ()
{
	short t;
	int a,b,c,d,i,j;
	fin>>t;
	for(t;t>0;t--)
	{
		fin>>a>>b>>c;
		d=euclid(a,b);
		if(c%d!=0)
			fout<<0<<" "<<0<<endl;
		else
		{
			a=a/d;
			b=b/d;
			c=c/d;
			for(i=1;i<500;i++)
			{
				for(j=1;j<500;j++)
				{
					
					if(i*a+j*b==c)
					{
						fout<<i<< " "<<j<<endl;
						goto loop1;
					}
					if(i*a-j*b==c)
					{
						fout<<i<< " "<<-j<<endl;
						goto loop1;
					}
					if(-i*a+j*b==c)
					{
						fout<<-i<< " "<<j<<endl;
						goto loop1;
					}
					if(-i*a-j*b==c)
					{
						fout<<-i<< " "<<-j<<endl;
						goto loop1;
					}
				}
			}
		}
		loop1:;
	}
}