Cod sursa(job #2722716)

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

using namespace std;

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

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

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

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