Cod sursa(job #3133792)

Utilizator BereaBerendea Andrei Berea Data 26 mai 2023 23:15:10
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;

ifstream cin("euclid3.in");
ofstream cout("euclid3.out");

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

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

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

int solve(int &x, int &y, int a, int b)
{
    if (b==0)
    {
        x=1;
        y=0;
        return a;
    }
    else
    {
        int s,t,d;
        d=solve(s,t,b,a%b);
        x=t;
        y=s-t*(a/b);
        return d;
    }

}

int main()
{

	int t;
	cin>>t;
	for (int i=1; i<=t; i++)
	{
		int A, B, C;
		cin>>A>>B>>C;
		int D, X, Y;
		D = solve( X, Y, A, B );

		if (C % D)
			cout<<0<<" "<<0<<"\n";
		else
			cout<<X*(C/D)<<" "<<Y*(C/D)<<"\n";
	}

	return 0;
}