Cod sursa(job #2489088)

Utilizator Iulia25Hosu Iulia Iulia25 Data 7 noiembrie 2019 21:51:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>

using namespace std;

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

int a, b, c, t;
pair <pair <int, int>, int> _x;

pair <pair <int, int>, int> eea(int a, int b)	 {
	pair <pair <int, int>, int> x, k;
  if (b == 0)	 {
    x.first.first = 1;
    x.first.second = 0;
    x.second = a;
    return x;
  }
  k = eea(b, a % b);
  x.first.first = k.first.second;
  x.first.second = k.first.first - a / b * k.first.second;
  x.second = k.second;
  return x;
}

int main()	{
	fin >> t;
	while (t--)	 {
		fin >> a >> b >> c;
		_x = eea(a, b);
		if (c % _x.second)	{
			fout << "0 0\n";
			continue;
		}
		fout << c / _x.second * _x.first.first << ' ' << c / _x.second * _x.first.second << '\n';
	}
	return 0;
}