Cod sursa(job #3297990)

Utilizator sonia.peiovPeiov Sonia sonia.peiov Data 25 mai 2025 17:56:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.11 kb
// https://infoarena.ro/problema/euclid3
// Se dau T ecuatii de forma a * x + b * y = c, cu coeficientii a, b si c. 
// Pentru fiecare dintre aceste ecuatii se cere aflarea unei perechi de numere intregi x y care sa satisfaca ecuatia, in cazul in care o astfel de pereche exista.

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

// Functia calculeaza coeficientii x si y astfel incat a * x + b * y = gcd(a, b) utilizand algoritmul lui Euclid extins si returneaza gcd(a, b).
int EuclidExtins(int a, int b, int& x, int& y)
{
	if (b == 0)	// cazul de baza al recurentei
	{
		x = 1;
		y = 0;
		return a; // gcd(a, 0) = a
	}
	else
	{
		int x1, y1;
		int gcd = EuclidExtins(b, a % b, x1, y1);
		x = y1;
		y = x1 - (a / b) * y1;
		return gcd;
	}
}

int main()
{
	ifstream fin("euclid3.in");
	ofstream fout("euclid3.out");

	if (!fin.is_open())
	{
		cerr << "Eroare la deschiderea fisierului de intrare!";
		return 1;
	}

	if (!fout.is_open())
	{
		cerr << "Eroare la deschiderea fisierului de iesire!";
		return 1;
	}

	int T;
	fin >> T;
	if (!(1 <= T && T <= 100))
	{
		cerr << "Nu se respecta restrictiile impuse. Numarul de ecuatii trebuie sa fie intre 1 si 100.";
		return 1;
	}

	while (T--)
	{
		int a, b, c;
		fin >> a >> b >> c;

		// Exemplele date ca date de intrare pe site nu respecta a <= b !
		/*
		if (!(-1000000000 <= a && a <= b && b <= 1000000000 && abs(c) <= 2000000000))
		{
			cerr << "Nu se respecta restrictiile impuse.";
			return 1;
		}
		*/

		// Aceste restrictii corespund datelor de intrare de pe site
		if (!(abs(a) <= 1000000000 && abs(b) <= 1000000000 && abs(c) <= 2000000000))
		{
			cerr << "Nu se respecta restrictiile impuse.";
			return 1;
		}

		int x, y;
		int gcd = EuclidExtins(a, b, x, y);

		if (c % gcd)
		{
			fout << "0 0" << endl; // daca c nu este divizibil cu gcd(a, b), nu exista solutii
		}
		else
		{
			x = x * (c / gcd); // scalarea solutiei
			y = y * (c / gcd); // scalarea solutiei
			fout << x << " " << y << endl; // afisarea solutiei
		}
	}

	fin.close();
	fout.close();
	return 0;
}