Cod sursa(job #2722731)

Utilizator Rares31100Popa Rares Rares31100 Data 13 martie 2021 11:34:18
Problema Algoritmul lui Euclid extins Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>

using namespace std;

long long euclid(long long a, long long b)
{
	while(b)
	{
		long long r = a % b;
		a = b;
		b = r;
	}
	
	return a;
}

void euclidExtins(long long a, long long b, long long &x, long long &y, long long &d)
{
	if(b)
	{
		euclidExtins(b, a % b, x, y, d);
		x = y;
		y = (d - a * x) / b;
	}
	else
	{
		d = a;
		x = 1;
		y = 0;
	}
}

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

int main()
{
	long long t, a, b, d;
	in >> t;
	while(t--)
	{
		in >> a >> b >> d;
		if(d % euclid(a, b) == 0)
		{
			long long x, y, c;
			euclidExtins(a, b, x, y, c);
			out << x * (d / c) << ' ' << y * (d / c) << '\n';
		}
		else
			out << -1 << '\n';
	}
	
	return 0;
}