Cod sursa(job #761155)

Utilizator ioana26Ioana Andronescu ioana26 Data 24 iunie 2012 23:31:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <stdlib.h>

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

int main () {
	int t;
	int a, b, c, d;
	int x, y;

	FILE *f_in = fopen("euclid3.in", "r");
	FILE *f_out = fopen("euclid3.out", "w");

	int i;
	fscanf(f_in, "%d", &t);
	for (i = 0; i < t; i++) {
		fscanf(f_in, "%d %d %d", &a, &b, &c);
		
		d = gcd_extended(a, b, &x, &y);
		printf("d: %d\n", d);
		if (c % d) {
			fprintf(f_out, "0 0\n");
		}
		else {
			fprintf(f_out, "%d %d\n", x * (c / d), y * (c / d));
		}
	}

	fclose(f_in);
	fclose(f_out);	
	return 0;
}