Cod sursa(job #185192)

Utilizator anoukAnca Dumitrache anouk Data 24 aprilie 2008 21:23:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <cstdio>
using namespace std;

int cmmdc(int A, int B, int &X, int &Y)
{
	if (!B)
	{
		X = 1;
		Y = 0;
		return A;
	}
	int X0, Y0, D;
	D = cmmdc(B, A % B, X0, Y0);
	X = Y0;
	Y = X0 - (A / B) * Y0;
	return D;	
}

int main()
{
	FILE *fin = fopen("euclid3.in", "r");
	FILE *fout = fopen("euclid3.out", "w");

	int N, A, B, C, D;
	fscanf(fin, "%d", &N);
	for (int i = 1; i <= N; i++)
	{
		fscanf(fin, "%d%d%d", &A, &B, &C);
		int X, Y;
		D = cmmdc(A, B, X, Y);
		if (C % D) fprintf(fout, "0 0\n");
		else       fprintf(fout, "%d %d\n", X * (C / D), Y * (C / D));
	}

	fclose(fin);
	fclose(fout);
	return 0;
}