Cod sursa(job #2080564)

Utilizator IulianBobocBoboc Iulian IulianBoboc Data 3 decembrie 2017 11:44:46
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<iostream>
#include<fstream>
using namespace std;

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

int main() {
	ifstream inFile("euclid3.in");
	ofstream outFile("euclid3.out");

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

	for (int i = 0; i < t; ++i) {
		inFile >> a >> b >> c;
		computeEuclidSolution(a, b, d, x, y);
		int factor = c / d;
		if (c%d != 0) {
			x = y = 0;
		}
		else {
			x *= factor;
			y *= factor;
		}
		outFile << x << " " << y << "\n";
	}
	inFile.close();
	outFile.close();
	return 0;
}