Cod sursa(job #758567)

Utilizator aranhilChivu Stefan Iulian aranhil Data 15 iunie 2012 23:45:48
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
FILE *f, *g;

int euclid_extins(long a, long b, long r, long &x, long &y) {
	if(b % r != 0)
		int cmmdc = euclid_extins(b, r, b % r, x, y);
	else {
		x = 1;
		y = - a / b;
		return r;
	}
	long tmp = y;
	y = x - y * (a / b);
	x = tmp;
}

int main() {
	long x, y, cmmdc, a, b, c;
	f = fopen("euclid3.in", "r");
	g = fopen("euclid3.out", "w");

	long n;
	fscanf(f, "%ld", &n);

	for(long i = 0; i < n; i++) {
		fscanf(f, "%ld %ld %ld", &a, &b, &c);
		cmmdc = euclid_extins(a, b, a % b, x, y);
		if(c % cmmdc == 0) 
			fprintf(g, "%ld %ld\n", int(double(x) * c / cmmdc), int(double(y) * c / cmmdc));
		else
			fprintf(g, "0 0\n");
	}

	return 0;
}