Cod sursa(job #2923716)

Utilizator KillHorizon23Orban Robert KillHorizon23 Data 18 septembrie 2022 13:05:06
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ui = size_t;
using pi = pair<int, int>;
	
#define IOS                           \
	ios_base::sync_with_stdio(false); \
	cin.tie(nullptr);                 \
	cout.tie(nullptr);
#define endl "\n"
#define VECTOR(v) \
	v.begin(), v.end()
#define FILE_INPUT(file)              \
	ifstream fin(file + ".in");       \
	ofstream fout(file + ".out"); 
	
template <typename T>
	struct Tuple{
		T first, second, third;
	};
	
const int MOD = (int)1e9 + 5;
const int NMAX = 1005;
const int di[] = {1, 0, -1, 0};
const int dj[] = {0, 1, 0, -1};
string const& task("euclid3");

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

int main(){
	IOS
	FILE_INPUT(task);
	
	int t;
	fin >> t;
	
	while (t--){
		ll a, b, c, x, y, d;
		fin >> a >> b >> c;
		
		euclidExtins(a, b, d, x, y);
		
		if (c % d != 0){
			fout << 0 << " " << 0 << endl;
		}
		else{
			fout << x * (c / d) << " " << y * (c / d) << endl;
		}
	}
	
	return 0;
}