Cod sursa(job #1339090)

Utilizator aimrdlAndrei mrdl aimrdl Data 10 februarie 2015 17:55:22
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>

#define MIN(a, b) (a < b) ? (a) : (b)
#define MAX(a, b) (a > b) ? (a) : (b)

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

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