Cod sursa(job #2670484)

Utilizator davidcotigacotiga david davidcotiga Data 9 noiembrie 2020 22:49:06
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <map>

using namespace std;

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

int gcd(int a, int b, int& x, int& y) {
	if (a == 0) {
		x = 0;
		y = 0;
		return b;
	}

	int x1, y1, d;
	d = gcd(b % a, b, x1, y1);

	x = y1 - (b / a) * x1;
	y = x1;

	return d;
}

int main() {
	int t;
	fin >> t;

	for (int info = 0; info < t; ++info) {

		int a, b, c;
		fin >> a >> b >> c;

		int x, y;
		int d = gcd(a, b, x, y);

		if (c % d)
			fout << 0 << " " << 0 << "\n";
		else
			fout << x * (c / d) << " " << y * (c / d) << "\n";
	}
	return 0;
}