Cod sursa(job #1537216)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 27 noiembrie 2015 00:48:34
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>


using namespace std;

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

int n;

int euclid(int a, int b, int* x, int* y) {

	if(b == 0) {
		
		*x = 1;
		*y = 0;
		return a;

	} else {

		int y0;
		int x0;

		int d = euclid(b, a % b, &x0, &y0);
		
		int c = a / b;

		*x = y0;
		*y = x0 - c * y0;
		return d;
	}
}


int main() {

	int a; int b; int c;

	int x; int y; int d;

	fin >> n;

	while(n--) {

		fin >> a >> b >> c;

		d = euclid(a, b, &x, &y);

		if(c % d != 0)
			fout << 0 << " " << 0 << '\n';
		else 
			fout << (int)(1ll * x * c / d) << " "<< (int)(1ll * y * c / d) << '\n'; 
			//fout << (int)(1LL* x * a * c / d  + 1ll *  b * y * c / d) << " " << c << '\n'; ; 
		
	}

	return 0;
}