Cod sursa(job #2098223)

Utilizator flibiaVisanu Cristian flibia Data 2 ianuarie 2018 16:16:12
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.54 kb
#include <bits/stdc++.h>

using namespace std;

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

int t, a, b, c, d, x, y; 

void gcd(int a, int b, int &d, int &x, int &y){
	if(!b){
		d = a;
		x = 1;
		y = 0;
	} else{
		int xx, yy;
		gcd(b, a % b, d, xx, yy);
		x = yy;
		y = xx - yy * (a / b);
	}
}

int main(){
	in >> t;
	while(t--){
		in >> a >> b >> c;
		gcd(a, b, d, x, y);
		if(c % d){
			out << "0 0\n";
			continue;
		}
		out << (long long)x * c / d << ' ' << (long long)y * c / d << '\n'; 
	}
	return 0;
}