Cod sursa(job #758557)

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

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

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

	int n;
	fscanf(f, "%d", &n);

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

	return 0;
}