Cod sursa(job #2706668)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 15 februarie 2021 16:56:21
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

int T,a, b, c;

int gcd(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

int main(){

	f >> T;
	while(T--){
		f >> a >> b >> c;
		int x, y;
		int d = gcd(a, b, x, y);
		if(c % d)
			g << "0 0\n";
		else 
			g << x * (c / d)  << " " << y * (c / d) << "\n";
	}
}