Cod sursa(job #708752)

Utilizator valiro21Valentin Rosca valiro21 Data 7 martie 2012 09:47:57
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include<fstream>
using namespace std;

void euclid(long a,long b,long &u,long&v,long&d)
{
	long u1,u2,u3,v1,v2,v3,c,r;
	
	u1=1;u2=0;
	v1=0;v2=1;
	
	if(b==0)
    {
        u=1;
        v=0;
        d=a;
        return;
    }
	
	while(b!=0)
	{
		c=a/b;
		r=a%b;
		if(r==0)
			break;
		u3=u1-c*u2;
		v3=v1-c*v2;
		
		u1=u2; u2=u3;
		v1=v2; v2=v3;
		
		a=b; b=r;
	}
	u=u2;
	v=v2;
	d=b;
}

int main()
{
	long a,b,c,d,u,v,n,j,sa,sb;
	
	freopen("euclid3.in","rt",stdin);
	freopen("euclid3.out","wt",stdout);
	
	scanf("%ld",&n);
	for(j=1;j<=n;j++)
	{
		scanf("%ld %ld %ld",&a,&b,&c);
	
		sa=sb=1;
	
		if(a<0)
			sa=-1,a=-a;
		if(b<0)
			sb=-1,b=-b;
	
		euclid(a,b,u,v,d);
		
		if(c%d!=0)
			printf("0 0\n");
		else 
		{
			u=u*(c/d);
			v=v*(c/d);
			u=u*sa;
			v=v*sb;
			
			printf("%ld %ld\n",u,v);
		}
	}
	
	return 0;
}