Cod sursa(job #356828)

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