Cod sursa(job #1455401)

Utilizator aimrdlAndrei mrdl aimrdl Data 27 iunie 2015 22:18:57
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>

//assume a < b
int euclid (int a, int b, int *x, int *y) {
	int r;
	if (a == 0) {
		*x = 0;
		*y = 1;
		return b;
	} else {
		r = euclid (b % a, a, x, y);
		int x0 = *x;
		*x = *y - x0 * (b / a);
		*y = x0;
	}
	
	return r;
}

int main (void) {
	FILE *in = fopen("euclid3.in", "r");
	FILE *out = fopen("euclid3.out", "w");
	
	int n;
	fscanf(in, "%d", &n);
	
	int x, y, a, b, c;
	for (int i = 0; i < n; ++i) {
		fscanf(in, "%d %d %d", &a, &b, &c);
		
		int lcd;
		if (a < b) { 
			lcd = euclid(a, b, &x, &y);
		}
		else {
			lcd = euclid(b, a, &y, &x);
		}
		
		if (c % lcd == 0) {
			c = c / lcd;
			fprintf(out, "%d %d\n", x * c, y * c);
		}	else {
			fprintf(out, "0 0\n");
		}
	}

	fclose(in);
	fclose(out);
	
	return 0;
}