Cod sursa(job #3121563)

Utilizator daristyleBejan Darius-Ramon daristyle Data 14 aprilie 2023 01:27:54
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.56 kb
#include <fstream>

using namespace std;

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

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

int main() {
	int tasks;
	fin >> tasks;

	for(int i = 0; i < tasks; ++i){
		int a, b, c, d, x, y;
		fin >> a >> b >> c;

		extended_euclid(a, b, d, x, y);
		
		if(c % d)
			c = 0;

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

	fin.close();
	fout.close();
	return 0;
}