Cod sursa(job #2639307)

Utilizator AndreiPaval03Andrei Paval AndreiPaval03 Data 1 august 2020 13:00:08
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>

using namespace std;

void euclidExtins(int a, int b, int &x, int&y, int&d)
{
	if (b) 
	{
		int x0, y0;
		euclidExtins(b, a % b, x0, y0, d);

		x = y0;
		y = x0 - a / b * y0; 
	} 
	else 
	{
		d = a;
		x = 1;
		y = 0; 
	}
}

int main()
{

	freopen("euclid3.in", "rt", stdin);
	freopen("euclid3.out", "wt", stdout);
	
    int t, a, b, c, d, x, y;

    cin >> t;
    while (t--)
    {
    	cin >> a >> b >> c;
    	
    	euclidExtins(a, b, x, y, d);
    	if (c % d == 0)
    		cout << x * c / d << ' ' << y * c / d << '\n';
    	else 
    		cout << "0 0\n";
    }

	return 0;
}