Cod sursa(job #267952)

Utilizator luk17Luca Bogdan luk17 Data 28 februarie 2009 15:53:10
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#define max(a,b) a>b?a:b
struct Vect
{
int x, y;
};
void atr(Vect &V,Vect V1){
	V.x=V1.x;V.y=V1.y;
}
Vect prod(Vect V,int q){
	V.x*=q;V.y*=q; return V;
}
void dif(Vect &V,Vect V1,Vect V2)
{ V.x=V1.x-V2.x;V.y=V1.y-V2.y;
}
int main()
{
	Vect v,v1,v0;
	int a,b,c,q,r,t,inv;
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	scanf("%d",&t);
	for(;t;t--)
	{
	scanf("%d%d%d",&a,&b,&c);
	v0.x=v1.y=1;
	v0.y=v1.x=0;
	inv=0;
	if(a<b)
	{
		r=a;
		a=b;
		b=r;
		inv=1;
	}
	while(b)
	{
		q=a/b;
		r=a%b;
		a=b;
		b=r;
		atr(v,v0);
		atr(v0,v1);
		dif(v1,v,prod(v0,q));
	}
	if(c%a)
		printf("0 0\n");
	else
		if(inv==0)
	printf("%d %d\n",v0.x*c/a,v0.y*c/a);
	else
		printf("%d %d\n",v0.y*c/a,v0.x*c/a);
	}
	return 0;
}