Cod sursa(job #2579148)

Utilizator TudorChirila11Tudor Chirila TudorChirila11 Data 12 martie 2020 00:00:08
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define N 200005
using namespace std;
typedef long long ll;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
ll n, m, i, j, a, b, x, y, c;
void euclid(ll a, ll b, ll &x, ll& y)
{
	//cout<<a<<' '<<b<<'\n';
	if(b==0)
	{
		y=0;
		x=1;
	}
	else{
		ll x0, y0;
		euclid(b,a%b,x0,y0);
		x=y0;
		y=x0-a/b*y0;
	}
}
int main()
{
	fin>>n;
	while(n)
	{
		--n;
		fin>>a>>b>>c;
		ll d=__gcd(a,b);
		if(c%d)
		{
			fout<<"0 0\n";
			continue;
		}
		euclid(a,b,x,y);
		fout<<x*c/d<<' '<<y*c/d<<'\n';
	}
	//euclid(a,b,x,y);
	//fout<<x<<' '<<y<<'\n';
}