Cod sursa(job #2038953)

Utilizator Tyler_BMNIon Robert Gabriel Tyler_BMN Data 14 octombrie 2017 10:16:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>

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

int t,a,b,c;


pair<long long, long long> Euclid_Extins(long long x, long long y) {
	if (y == 0)
		return { 1,0 };
	pair<long, long> p = Euclid_Extins(y, x%y);
	return { p.second, p.first - (x / y)*p.second };
}

int main() {
	fin >> t;
	for (int i = 0; i < t; i++) {
		fin >> a >> b >> c;
		pair<long long, long long> p = Euclid_Extins(a, b);
		long long d = a * p.first + b * p.second;
		if (c%d != 0)
			fout << "0 0\n";
		else {
			fout << p.first*(c / d) << " " << p.second*(c / d) << "\n";
		}
	}
}