Cod sursa(job #1690918)

Utilizator andreilucaLuca Andrei andreiluca Data 16 aprilie 2016 11:38:05
Problema Floyd-Warshall/Roy-Floyd Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>

FILE *in, *out;

//int cmmdc(int,int);
void euclid_extins(int a, int b,int &d, int &x, int &y);
int n;
int main()
{
	in = fopen("euclid3.in","r");
	out = fopen("euclid3.out", "w");
	fscanf(in, "%d", &n);
	int a, b,c,x,y,d;
	for (int i = 0; i < n; i++)
	{
		x = y = 0;
		fscanf(in, "%d%d%d", &a, &b,&c);
		euclid_extins(a, b, d, x, y);
		if (c%d == 0)
			fprintf(out, "%d %d\n", x*(c / d), y*(c / d));
		else
			fprintf(out, "%d %d\n", 0, 0);
	}
	//printf("%d", cmmdc(45, 35));

	return 0;
}
/*
int cmmdc(int a, int b)
{
	int rest;
	if (b > a)
		std::swap(a, b);
	if (a%b == 0)
		return b;
	rest = a%b;
	while (rest)
	{
		rest = a%b;
		a = b;
		b = rest;
	}
	return a;
	
}*/
void euclid_extins(int a,int b,int &d,int &x,int &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		d = a;
	}
	else
	{
		int x0, y0;
		euclid_extins(b, a%b,d, x0, y0);
		x = y0;
		y = x0 - (a / b)*y0;
	}
}