Cod sursa(job #356823)

Utilizator IlieeUngureanu Ilie Iliee Data 16 octombrie 2009 19:18:14
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<stdio.h>
long long a[150],b[150],c,t,A,B,R,k,i,x[150],y[150],q[150];
void read(), solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	scanf("%lld",&t);
}
void solve()
{
	for(;t;t--)
	{
		scanf("%lld%lld%lld",&a[1],&b[1],&c);
		if(c<0){a[1]=-a[1];b[1]=-b[1];c=-c;}
		a[0]=a[1]<0?-1LL:1LL;a[1]=a[0]*a[1];
		b[0]=b[1]<0?-1LL:1LL;b[1]=b[0]*b[1];
		A=a[1];B=b[1];
		while(B){R=A%B;A=B;B=R;}
		if(c%A)
		{
			printf("0 0\n");continue;
		}
		for(k=1;;k++)
		{
			a[k+1]=b[k];
			b[k+1]=a[k]%b[k];
			q[k]=a[k]/b[k];
			if(!b[k+1])
			{
				k++; break;
			}
		}
		x[k]=c/a[k];
		y[k]=0;
		for(i=k-1;i>=1;i--)
		{
			x[i]=y[i+1];
			y[i]=x[i+1]-q[i]*y[i+1];
		}
		x[1]*=a[0];
		y[1]*=b[0];
		printf("%lld ",x[1]);
		printf("%lld\n",y[1]);
	}
}