Cod sursa(job #656301)

Utilizator geniucosOncescu Costin geniucos Data 4 ianuarie 2012 14:11:07
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
using namespace std;
long long 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;
	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("%d",&a);
	scanf("%d",&b);
	scanf("%d",&c);
	x1=cmmdc(a,cmmdc(b,c));
	a=a/x1;
	b=b/x1;
	c=c/x1;
	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];
		}
		printf("%d ",x[1]);
		printf("%d\n",y[1]);
	}
}
return 0;
}