Cod sursa(job #758578)

Utilizator aranhilChivu Stefan Iulian aranhil Data 16 iunie 2012 00:06:22
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
FILE *f, *g;
long x, y, cmmdc, a, b, c;

inline long euclid_extins(long a, long b, long &x, long &y) {
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}

	cmmdc = euclid_extins(b, a % b, x, y);

	long tmp = y;
	y = x - y * (a / b);
	x = tmp;
	return cmmdc;
}

int main() {
	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, x, y);
		if(c % cmmdc == 0) 
			fprintf(g, "%ld %ld\n", long(double(x) * c / cmmdc), long(double(y) * c / cmmdc));
		else
			fprintf(g, "0 0\n");
	}

	return 0;
}