Cod sursa(job #1537207)

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


using namespace std;

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

int n;

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

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

	} else {

		int y0;
		int x0;

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

		*x = y0;
		*y = 1LL* x0 - c * y0;
	}
}


int main() {

	int a; int b; int c;

	int x; int y; int d;

	fin >> n;

	while(n--) {

		fin >> a >> b >> c;

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

		if(c % d != 0)
			fout << 0 << " " << 0 << '\n';
		else 

			fout << x * c / d << " " << y * c / d << '\n'; 
		
	}

	return 0;
}