Cod sursa(job #526021)

Utilizator Light532Light 532 Light532 Data 27 ianuarie 2011 00:50:43
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <stdio.h>


typedef struct {
	int x;
	int y;
}Vcorp;
	
int gcd(int a,int b)
{
	int r;
	if(b == 0 && a == 0)
	{
		return -1;
	}
	/*
	if(b == 0 || a == 0)
	{
		return 0;
	}
	*/
	if(a<b)
	{
		r = a;
		a = b;
		b = r;
	}

	while(b>0)
	{
		r = a%b;
		a = b;
		b = r;
	}
	return a;
}


int ExtendedEuclid(int a,int b,int &alpha, int &beta)
{
	int Va,Va0,Va1;
	int Vb,Vb0,Vb1;
	int q,r;
	Va0 = 1;
	Vb0 = 0;
	Va1 = 0;
	Vb1 = 1;
	while(b!=0)
	{ 
		q = a / b;
		r = a % b;
		a = b;
		b = r;
		//V = V0;
		Va = Va0;	Vb = Vb0;
		
		//V0 = V1;
		Va0 = Va1;	Vb0 = Vb1;
	
		//V1 = V -qV1
		Va1 = Va - q * Va1;
		Vb1 = Vb - q * Vb1;
	}
	Va = Va0;
	Vb = Vb0;
	alpha = Va;
	beta = Vb;
	return 0;
}

int DiophantineEquation(int a,int b,int c, int &x, int &y)
{
	int d;
	int alpha,beta;
	int siga=a;
	int sigb=b;
	int sigc=c;
	if(a<0)
		a=-a;
	if(b<0)
		b=-b;
	d = gcd(a,b);
	if(d==-1)
	{
		return 0; //no solution	
	}
	ExtendedEuclid(a,b,alpha,beta);
	if(c % d == 0)
	{
		if(c<0)
			c = -c;
		if(siga<0)
			alpha = -alpha;
		if(sigb<0)
			beta = -beta;
		c = c / d;
		x = alpha * c;
		y = beta * c;

		return 1; //solution;
	}
	return 0;//no solution;
}
int main()
{
	int i,n,a,b,c,x,y;
	FILE *f,*g;
	f = fopen("euclid3.in","r");
	g = fopen("euclid3.out","w");
	fscanf(f,"%d",&n);
	for(i=0;i<n;i++)
	{
		fscanf(f,"%d %d %d",&a,&b,&c);
		x=0;
		y=0;
		DiophantineEquation(a,b,c,x,y);
		fprintf(g,"%d %d\n",x,y);
	}
	fclose(f);
	fclose(g);
	return 0;	
}