Cod sursa(job #2616304)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 18 mai 2020 00:21:44
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <bits/stdc++.h>

using namespace std;

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

inline int gcd( int A, int B, int &X, int &Y ) {
	if (B == 0) {
		X = 1;
		Y = 0;
		return A;
	}
	int X0, Y0, D;
	D = gcd (B, A % B, X0, Y0 );
	X = Y0;
	Y = X0 - (A / B) * Y0;
	return D;
}

int main() {
	int T;
	fin >> T;
	for ( ; T; T--) {
		int A, B, C;
		fin >> A >> B >> C;
		int D, X, Y;
		D = gcd( A, B, X, Y );
		if (C % D) fout << "0 0\n";
		else fout << X * (C / D) << " " << Y * (C / D) << '\n';
	}
	fin.close ();
	fout.close ();
	return 0;
}