Cod sursa(job #1463992)

Utilizator creativedoughnutCreative Doughnut creativedoughnut Data 21 iulie 2015 23:44:30
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

// --- basics
#define int16 short
#define int32 int
#define int64 int long long
#define uint16 unsigned int16
#define	uint32 unsigned int32
#define uint64 unsigned int64

// --- prototypes
void gcd_extended(int32 a, int32 b, uint32 &result, int32 &x, int32 &y);

/// --- input/output files
#define INPUT_FILE	"euclid3.in"
#define	OUTPUT_FILE	"euclid3.out"

int main()
{
	freopen(INPUT_FILE, "r", stdin);
	freopen(OUTPUT_FILE, "w", stdout);

	uint16 T;
	scanf("%hd", &T);
	for (uint16 i = 0; i < T; i++)
	{
		int32 a, b, c;
		scanf("%d %d %d", &a, &b, &c);

		int32 x, y;
		uint32 gcd;
		gcd_extended(a, b, gcd, x, y);

		if (c % gcd != 0)
		{
			printf("0 0\n");
		}
		else
		{
			printf("%d %d\n", x * (c / (int32)gcd), y * (c / (int32)gcd));
		}
	}

	return 0;
}


// --- functions
void gcd_extended(int32 a, int32 b, uint32 &result, int32 &x, int32 &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		result = (uint32)(a);
		return;
	}

	int32 x0, y0;
	gcd_extended(b, a % b, result, x0, y0);

	x = y0;
	y = x0 - (a / b) * y0;
}