Cod sursa(job #2487864)

Utilizator FlorianMarcuMarcu Florian Cristian FlorianMarcu Data 5 noiembrie 2019 20:12:31
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
std::ifstream fin("euclid3.in");
std::ofstream fout("euclid3.out");

long long max(long long a, long long b) {
	if (a > b)
		return a;
	else return b;
}


void euclid_extins(long long *x, long long *y, long long a, long long b, long long c)
{
	if (b == 0)
	{
		*x = 1;
		*y = 0;
	}
	else {
		long long x0, y0;
		euclid_extins(&x0, &y0, b, a%b, c);
		*x = y0;
		*y = x0 - (a / b)* y0;
	}
}
long long cmmdc(int a, int b)
{
	if (a*b != 0)
		if (a < b)
			return cmmdc(a, b%a);
		else
			return cmmdc(a%b, b);
	else return max(a, b);
}
int main()
{
	short T;
	fin >> T;
	long long a, b, c;
	long long x = 0, y = 0;
	for (int i = 0; i < T; i++) {
		fin >> a >> b >> c;
		long long d = cmmdc(a, b);
		if (c%d != 0)
			fout << 0 << " " << 0 << std::endl;
		else
			{
			euclid_extins(&x, &y, a, b, d);
			fout << x*c/d << " " << y*c/d << std::endl;
			}
		}
}