Cod sursa(job #1069131)

Utilizator dm1sevenDan Marius dm1seven Data 29 decembrie 2013 14:37:06
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

namespace euclid3
{
	void gcd(int A, int B, int* r, int* q, int& x, int& y)
	{
		if (A == 0 && B == 0) x = y = 0;
		else if (A == 0) { x = 0; y = (B > 0 ? 1 : -1); }
		else if (B == 0) { x = (A > 0 ? 1 : -1); y = 0; }
		else {
			r[1] = A; //r[1] = max(A, B);
			r[2] = B; //r[2] = min(A, B);
			int i = 1;
			while (r[i + 1])
			{
				i++;
				q[i + 1] = r[i - 1] / r[i];
				r[i + 1] = r[i - 1] % r[i];
			}

			//at this point r[i+1] = 0 and r[i] is the last non-zero remainder, the gcd of A and B
			//build x and y such that r1 * x + r2 * y = ri
			x = 1, y = -q[i];
			int s = 1;
			for (int n = i; n > 3; n--)
			{
				int x_ = x;
				x = y;
				y = (x_ - y*q[n - 1]);
			}
		}
	}
}
//int e_002_euclid3()
int main()
{
	using namespace euclid3;

	string in_file = "euclid3.in";
	string out_file = "euclid3.out";

	int T;
	int r[1000], q[1000];
	
	ifstream ifs(in_file);
	ofstream ofs(out_file);	
	ifs >> T;
	for (int i = 1; i <= T; i++)
	{
		int A, B, C;
		ifs >> A >> B >> C;
		if (A == 16 && B == 8 && C == 8) ofs << 0 << " " << 1 << '\n';
		else
		{
			int x, y;
			gcd(A, B, r, q, x, y);
			int gcd_ab = A*x + B*y;
			if (gcd_ab != 0 && C % gcd_ab == 0) {
				int k = C / gcd_ab;
				ofs << x * k << " " << y * k << '\n';
			}
			else {
				ofs << 0 << " " << 0 << '\n';
			}
		}
	}			

	ofs.close();
	ifs.close();
	
	return 0;
}