Cod sursa(job #3372146)

Utilizator mihalachecostin.danielMihalache Costin-Daniel mihalachecostin.daniel Data 2 noiembrie 2026 17:08:49
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

long long euclid(long long a, long long b, long long& x, long long& y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	long long x1, y1;
	long long d = euclid(b, a % b, x1, y1);
	x = y1;
	y = x1 - (a / b) * y1;
	return d;
}

int main()
{
	int T;
	f >> T;
	for(int t=0;t<T;t++)
	{
		long long a, b, c, x0, y0;
		f >> a >> b >> c;
		long long d = euclid(a, b, x0, y0);
		if (d < 0)
		{
			d = -d;
			x0 = -x0;
			y0 = -y0;
		}

		if (d == 0 || c % d != 0)
		{
			g << "0 0\n";
			continue;
		}

		long long x, y;
		if (b == 0)
		{
			x = c / a;
			y = 0;
		}
		else
		{
			x = x0 * (c / d);
			long long step = (b < 0 ? -b : b) / d;
			x = ((x % step) + step) % step;
			y = (c - a * x) / b;
		}
		g << x << " " << y << endl;
	}
}