Cod sursa(job #2672111)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 13 noiembrie 2020 07:16:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
//ALEXANDRU MICLEA

#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>
#include <assert.h>

using namespace std;

#include <fstream>
//ifstream cin("input.in"); ofstream cout("output.out");
ifstream cin("euclid3.in"); ofstream cout("euclid3.out");

//VARIABLES



//FUNCTIONS

void euclid(long long a, long long b, long long& d, long long& x, long long& y) {
	if (b == 0) {
		d = a;
		x = 1; y = 0;
		return;
	}

	long long x1, y1;
	euclid(b, a % b, d, x1, y1);
	x = y1;
	y = x1 - (a / b) * y1;
}

//MAIN

int main() {

	long long n; cin >> n;

	while (n--) {
		long long a, b, c, d, x, y;
		cin >> a >> b >> c;
		euclid(a, b, d, x, y);
		if (c % d != 0) {
			cout << 0 << " " << 0 << '\n';
			continue;
		}
		long long m = c / d;
		cout << m * x << " " << m * y << '\n';
	}

	return 0;

}