Cod sursa(job #2722747)

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

using namespace std;

long long euclid(long long a, long long b)
{
	a = abs(a);
	b = abs(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
	{
		x = d / a;
		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;
			euclidExtins(a, b, x, y, d);
			out << x << ' ' << y << '\n';
		}
		else
			out << "0 0\n";
	}
	
	return 0;
}