Cod sursa(job #503232)

Utilizator razyelxrazyelx razyelx Data 22 noiembrie 2010 00:43:41
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include <stdio.h>

FILE *fin = fopen("euclid3.in", "r");
FILE *fout= fopen("euclid3.out","w");

long long gcd(long long a, long long b, long long &x, long long &y){
	if (b == 0){
		x = 1;
		y = 0;
		return a;
	} 
	long long x0, y0, d;
		
	d = gcd(b,a%b,x0,y0);
		
	x = y0;
	y = x0 - (a/b) * y0;
		
	return d;
	
}

int main(){
	long long a,b,c,x,y,d,t;
	
	fscanf(fin, "%lld", &t);
	
	while(t){
	
		fscanf(fin,"%lld %lld %lld",&a,&b,&c);
			
		d = gcd(a,b,x,y);
		
		if (c%d)
			fprintf(fout, "0 0\n");
		else
				fprintf(fout, "%lld %lld\n", x * (c/d), y * (c/d));
		t--;
	}
	return 0;
}