Cod sursa(job #3317708)

Utilizator teodor_tohteodor toh teodor_toh Data 24 octombrie 2025 23:59:50
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include<iostream>
#include<fstream>
#include <numeric>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

struct NUMS
{
	int a;
	int b;
	int x;
	int y;
};
long long int n, a, b, c, minDiv;
unsigned long long gcd(unsigned long long a1, unsigned long long b1)
{
	while (b1)
	{
		unsigned long long r = a1 % b1;
		a1 = b1;
		b1 = r;
	}
	return a1;
}
NUMS reverseEuclid(unsigned long long a1, unsigned long long b1)
{
	NUMS ret;
	if (a1 % b1 == 1)
	{
		ret.a = a1;
		ret.b = b1;
		ret.x = 1;
		ret.y = (a1 / b1) * (-1);
		return ret;
	}
	else
	{
		ret = reverseEuclid(b1, a1 % b1);
		int aux = ret.x;
		ret.b = ret.a;
		ret.a = a1;
		ret.x = ret.y;
		ret.y = aux + ret.y * (a1 / b1) * -1;
	}
	return ret;
}
int main()
{
	bool aSign = 1, bSign = 1, cSign = 1;
	fin >> n;
	for (int i = 0; i < n; i++)
	{
		fin >> a >> b >> c;
		if (a < 0)
			aSign = 0;
		if (b < 0)
			bSign = 0;
		if (c < 0)
			cSign = 0;
		minDiv = gcd(a, b);
		if (c % minDiv > 0)
		{
			fout << "0 0\n";
			cout << "0 0\n";
			continue;
		}
		NUMS ret;
		if (b == minDiv)
		{
			ret.a = a / minDiv;
			ret.b = b / minDiv;
			ret.x = 1;
			ret.y = (a / minDiv) / (b / minDiv) - 1;
		}
		else
		{
			ret = reverseEuclid(a / minDiv, b / minDiv);
		}
		
		ret.a *= minDiv;
		ret.b *= minDiv;
		ret.x *= c / minDiv;
		ret.y *= c / minDiv;
		if (cSign == 0)
		{
			ret.x *= -1;
			ret.y *= -1;
		}
		if (aSign == 0)
			ret.x *= -1;
		if (bSign == 0)
			ret.y *= -1;
		fout << ret.x << " " << ret.y << "\n";
		cout << ret.x << " " << ret.y << "\n";
	}
}