Cod sursa(job #3282607)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 6 martie 2025 10:49:52
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

long long ext_gcd(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1, y = 0;
		return a;
	}
	else {
		long long nx, ny, g;
		g = ext_gcd(b, a % b, nx, ny);
		x = ny;
		y = nx - (a / b) * x;
		return g;
	}
}

int main() {
	int t;
	fin >> t;
	while (t--) {
		long long a, b, c, x, y;
		fin >> a >> b >> c;
		long long g = ext_gcd(a, b, x, y);
		if (c % g) {
			fout << "0 0\n";
		}
		else {
			x *= c / g;
			y *= c / g;
			fout << x << " " << y << "\n";
		}
	}
}