Cod sursa(job #3317835)

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

long long int n, a, b, c, minDiv, d, x, y;
long long int gcd(int a1, int b1)
{
	while (b1)
	{
		int r = a1 % b1;
		a1 = b1;
		b1 = r;
	}
	return a1;
}
void euclid(long long int a, long long int b, long long int& d, long long int& x, long long int& y)
{
	if (b == 0)
	{
		d = a;
		x = 1, y = 1;
	}
	else
	{
		long long int x1, y1;
		euclid(b, a % b, d, x1, y1);
		x = y1;
		y = x1 - a / b * y1;
	}
}
int main()
{
	bool aSign = 1, bSign = 1, cSign = 1;
	fin >> n;
	for (int i = 0; i < n; i++)
	{
		fin >> a >> b >> c;
		aSign = 1;
		bSign = 1;
		cSign = 1;
		if (a < 0)
			aSign = 0;
		if (b < 0)
			bSign = 0;
		if (c < 0)
			cSign = 0;
		a = abs(a);
		b = abs(b);
		c = abs(c);
		minDiv = gcd(a, b);
		if (c % minDiv > 0)
		{
			fout << "0 0\n";
			cout << "0 0\n";
			continue;
		}
		euclid(a, b, d, x, y);
		
		x *= c / minDiv;
		y *= c / minDiv;
		
		if (cSign == 0)
		{
			x *= -1;
			y *= -1;
		}
		if (aSign == 0)
			x *= -1;
		if (bSign == 0)
			y *= -1;
		fout << x << " " << y << "\n";
		cout << x << " " << y << "\n";
	}
}