Cod sursa(job #266132)

Utilizator iondionGeorge Pascu iondion Data 24 februarie 2009 22:05:47
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#define TMAX 100
int T;

int cmmdc( int a, int b, int& X, int& Y )
{
				int q,r;
				int X1=1, Y1=0, X2=0, Y2=1;
				while(b)
				{
								q = a/b;
								r = a%b;
								a = b;
								b = r;
								X = X1; Y = Y1;
								X1 = X2; Y1 = Y2;
								X2 = X-q*X2;
								Y2 = Y-q*Y2;
				}
				X = X1; Y=Y1;
				return a;

}

int main()
{
	int X, Y, S, a, b, d;
	FILE *in = fopen( "euclid3.in", "r" );
	FILE *out = fopen( "euclid3.out", "w" );

	fscanf( in,"%d", &T );
	for( int i=0; i<T; i++ )
	{
		fscanf(in, "%d %d %d", &a, &b, &S );
		d = cmmdc( a, b, X, Y );
		if( S%d==0 )
			fprintf(out, "%d %d\n", X*(S/d), Y*(S/d) );
		else
						fprintf(out,"0 0\n");
	}
	fclose(in); fclose(out);	
	return 0;
}