Cod sursa(job #3203696)

Utilizator AsandeiStefanAsandei Stefan-Alexandru AsandeiStefan Data 14 februarie 2024 10:49:46
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
#include <cmath>

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

int n, a, b, c;

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() {
    fin >> n;
    while(n--) {
        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;
}