Cod sursa(job #1793129)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 30 octombrie 2016 19:47:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>

#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

#include <algorithm>
#include <functional>
#include <utility>

#include <cstring>
#include <ctime>
#include <cstdlib>

#define LL long long
#define pb push_back
#define mp make_pair

using namespace std;

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

int main() {

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

	int t;
	for (cin >> t; t; --t) {
		int x, y, a, b, c, d;

		cin >> a >> b >> c;
		euclid(a, b, x, y, d);

		if (c % d == 0) {
			cout << c / d * x << ' ' << c / d * y << '\n';
		}
		else cout << "0 0\n";
	}

	return 0;
}