Cod sursa(job #2802208)

Utilizator Langa_bLanga Radu Langa_b Data 17 noiembrie 2021 19:12:00
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
using namespace std;
ifstream cin("euclid3.in");
ofstream cout("euclid3.out");
long long n;
int main()
{
	cin >> n;
	for (long long i = 1; i <= n; i++)
	{
		long long a, b, c, x, y;
		cin >> a >> b >> c;
		long long aux1 = a;
		long long aux2 = b;
		long long r;
		while (aux2 != 0)
		{
			r = aux1 % aux2;
			aux1 = aux2;
			aux2 = r;
		}
		long long d = aux1;
		if (c % d != 0)
		{
			cout << 0 << ' ' << 0 << '\n';
		}
		else
		{
			pair<long long, long long> per1, per2;
			per1 = { 1, 0 };
			per2 = { 0, 1 };
			while (b != 0)
			{
				long long cat;
				r = 0;
				r = a % b;
				cat = a / b;
				per1.first = per1.first - cat * per2.first;
				per1.second = per1.second - cat * per2.second;
				pair<long long, long long> auxi = per1;
				per1 = per2;
				per2 = auxi;
				a = b;
				b = r;
			}
			x = per1.first;
			y = per1.second;
			cout << x * c / d << ' ' << y * c / d << '\n';
		}
	}
}