Cod sursa(job #2161907)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 11 martie 2018 21:55:16
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#define gcd(x, y) __gcd((x), (y))
using namespace std;

ifstream fi("euclid3.in");
ofstream fo("euclid3.out");

using i64 = long long;


i64 xa, ya, xb, yb, x, y;

static void euclid(i64 a, i64 b) {
	if (a == 0) {
		x = xb, y = yb;
		return; }
	if (b == 0) {
		x = xa, y = ya;
		return; }

	if (abs(a) > abs(b)) {
		xa-= xb * (a / b);
		ya-= yb * (a / b);
		euclid(a % b, b); }
	else {
		xb-= xa * (b / a);
		yb-= ya * (b / a);
		euclid(a, b % a); } }

static void solve() {
	i64 a, b, c, g;

	xa = 1, ya = 0;
	xb = 0, yb = 1;

	fi >> a >> b >> c;

	g = gcd(a, b);

	if (c % g) {
		fo << "0 0\n";
		return; }

	a/= g; b/= g; c/= g;
	a*= c, b*= c;

	euclid(a, b);

	fo << x * c << ' ' << y * c << '\n'; }

int main() {
	int tsk;

	fi >> tsk;
	while (tsk--)
		solve();

	return 0; }