Cod sursa(job #656348)

Utilizator geniucosOncescu Costin geniucos Data 4 ianuarie 2012 15:04:41
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<stdio.h>
using namespace std;
long long x11,y11,i1,y1,j,x1,n,i,a,b,c,nr,x[1002],y[1002],k[1002];
long long cmmdc(long long a,long long b)
{
	long long r;
	if(a<0) a=a*-1;
	if(b<0) b=b*-1;
	while(b!=0)
	{
		r=a%b;
		a=b;
		b=r;
	}
	return a;
}
int main()
{
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
scanf("%d",&n);
for(i1=1;i1<=n;i1++)
{
	nr=0;
	scanf("%lld",&a);
	scanf("%lld",&b);
	scanf("%lld",&c);
	x1=cmmdc(a,cmmdc(b,c));
	a=a/x1;
	b=b/x1;
	c=c/x1;
	x11=0;
	y11=0;
	if(a<0)
	{
		a=a*-1;
		x11=1;
	}
	if(b<0)
	{
		b=b*-1;
		y11=1;
	}
	x1=cmmdc(a,b);
	if(x1>1) printf("0 0\n");
	else
	{
		while(b>1)
		{
			x1=a%b;
			y1=a/b;
			nr++;
			k[nr]=y1;
			a=b;
			b=x1;
		}
		x[nr+1]=1;
		y[nr+1]=c-a;
		for(i=nr+1;i>=2;i--)
		{
			x[i-1]=y[i];
			y[i-1]=x[i]-k[i-1]*y[i];
		}
		if(x11==1) x[1]=x[1]*-1;
		if(y11==1) y[1]=y[1]*-1;
		printf("%lld ",x[1]);
		printf("%lld\n",y[1]);
	}
}
return 0;
}