Cod sursa(job #3243296)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 17 septembrie 2024 11:10:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
typedef long long ll;
typedef pair<ll,ll> pll;
ll t,a,b,c;
void solve()
{
	fin>>a>>b>>c;
	ll g=__gcd(a,b);
	if(c%g!=0)
	{
		fout<<"0 0\n";
		return;
	}
	a/=g;
	b/=g;
	c/=g;
	pll Va={1,0};
	pll Vb={0,1};
	while(b!=0)
	{
		ll r=a%b;
		ll cat=a/b;
		pll Vr;
		Vr.first=Va.first-Vb.first*cat;
		Vr.second=Va.second-Vb.second*cat;
		a=b;
		b=r;
		Va=Vb;
		Vb=Vr;
	}
	fout<<Va.first*c<<' '<<Va.second*c<<'\n';
}
int main()
{	
	ios_base::sync_with_stdio(false);
	fin.tie(0);
	fin>>t;
	while(t--)
		solve();
	return 0;
}