Cod sursa(job #792516)

Utilizator vlad96Vlad Zuga vlad96 Data 27 septembrie 2012 14:10:35
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>

long long a, b, c, d, x, y;
int t;
FILE *fis = fopen ("euclid3.in", "r");
FILE *fis2 = fopen ("euclid3.out", "w");

void read ()
{
	fscanf(fis, "%lld %lld %lld", &a, &b, &c);
}

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

void write (int v1, int v2)
{
	fprintf(fis2, "%lld %lld\n", v1, v2);
}

int main ()
{
	fscanf(fis, "%d", &t);
	while (t)
	{
		read ();
		euclid (a, b, x, y, d);
		if ( c % d != 0 )
			write(0,0);
		else
			write(x*(c/d), y*(c/d));
		t--;
	}
	fclose(fis);
	fclose(fis2);
	return 0;
}