Cod sursa(job #3201165)

Utilizator defaultPercyval Sultanov default Data 6 februarie 2024 22:48:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include <bits/stdc++.h>
using namespace std;
long long ai,bi,ci,t,x,y,s;

long long gcdex(long long a,long long b,long long &x,long long &y)
{
	if (b==0)
	{
		x=1;
		y=0;
		return a;
	}
	long long x1,y1;
	long long d=gcdex(b,a%b,x1,y1);
	x=y1;
	y=x1-y1*(a/b);
	return d;
}

int main()
{
	freopen("euclid3.in","r",stdin);
	freopen("euclid3.out","w",stdout);
	cin >> t ;
	while (t--)
	{
		cin >> ai >> bi >> ci ;
		s=gcdex(ai,bi,x,y);
		if (ci%s)printf("0 0\n");
		else printf("%d %d \n",x*(ci/s),y*(ci/s));
	}
    return 0;
}