Cod sursa(job #665412)

Utilizator tomescu_alinTomescu Alin tomescu_alin Data 22 ianuarie 2012 01:08:51
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <cassert>
#include <algorithm>

struct pair {
	long x, y;
	
	pair(long _x, long _y) : x(_x), y(_y) {}
};

void print(pair p)
{
	std::cout << "(" << p.x << ", " << p.y << ")" << std::endl;
}

void printGcd(pair p, long a, long b)
{
	std::cout << "GCD is " << a * p.x + b * p.y << std::endl;
}

pair euclid(long a, long b)
{
	long init_a = a, init_b = b;
	assert(a >= b);
	
	pair prev(1, 0);
	pair curr(0, 1);
	
	// print(prev);
	// print(curr);
	
	while(b != 0)
	{	
		//print(curr);
		
		long q = a / b;
		long r = a % b;
		
		pair old = curr;
		
		curr.x = prev.x - q * curr.x;
		curr.y = prev.y - q * curr.y;
		prev = old;
		
		a = b;
		b = r;
	}
	
	// printGcd(prev, init_a, init_b);
	
	return prev;
}

int main(int argc, char ** argv)
{
	std::ifstream fin("euclid3.in");
	std::ofstream fout("euclid3.out");
	
	if(!fin || !fout)
		return -1;
	
	unsigned int n;
	fin >> n;
	
	for(unsigned int i = 0; i < n; i++)
	{
		long a, b, c;
		fin >> a >> b >> c;
		
		bool swapped = false;
		if(a < b)
		{
			std::swap(a, b);
			swapped = true;
		}
		
		pair sol = euclid(a, b);
		
		if(swapped) { 
			std::swap(sol.x, sol.y);
			std::swap(a, b);
		}
		
		long gcd = a * sol.x + b * sol.y;
		
		if(c % gcd != 0)
		{
			fout << "0 0" << std::endl;
		}
		else
			fout << sol.x * (c / gcd) << " " << sol.y * (c / gcd) << std::endl;
	}
	
	return 0;
}