Cod sursa(job #3139646)

Utilizator MilitaruMihai2022Millitaru Mihai MilitaruMihai2022 Data 30 iunie 2023 15:31:32
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>

using namespace std;

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

inline int eucl( int A, int B, int &X, int &Y )
{
	if (B == 0)
	{
		X = 1;
		Y = 0;
		return A;
	}

	int X0, Y0, D;
	D = eucl( B, A % B, X0, Y0 );

	X = Y0;
	Y = X0 - (A / B) * Y0;
	return D;
}

int main()
{
    int k;
    f >> k;
    while ( k-- )
    {
        int x, y, d, a, b, c;
        f >> a >> b >> c;
        d = eucl ( a, b, x, y );
        if ( c %  d  )
            g << 0 << ' ' << 0 << '\n';
        else
            g << x*(c / d) << ' ' << y*(c / d )<< '\n';
    }
    return 0;
}