Cod sursa(job #2361782)

Utilizator baltoi.teodorTeodor Baltoi baltoi.teodor Data 2 martie 2019 18:46:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
typedef long long ll;
int T,a,b,c;

int gcd( ll A, ll B, ll &X, ll &Y )
{
	if (B==0)
	{
		X=1;
		Y=0;
		return A;
	}
	ll  X0,Y0,D;
	D=gcd( B, A % B, X0, Y0 );
	X=Y0;
	Y=X0-(A/B)*Y0;
	return D;
}
int main()
{
    ll x,y,d;
    fin>>T;
    for(int i=1;i<=T;++i)
    {
        fin>>a>>b>>c;
        // a*x+b*y=c ;
        d=gcd(a,b,x,y);
        //sol daca c%d==0
        if(c%d) fout<<"0 0\n";
        else {
            //inmultesc relatia cu c/d
            fout<<x*(c/d)<<" "<<y*(c/d)<<"\n";
        }
    }
    return 0;
}