Cod sursa(job #2841667)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 30 ianuarie 2022 11:00:27
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");

int euclid(int a,int b,long long &x,long long &y)
{
    int g,val;
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    g=euclid(b,a%b,x,y);
    val=y;
    y=x-(a/b)*y;
    x=val;
    return g;
}

void solve()
{
	int a,b,c;
	long long x,y;
	fin>>a>>b>>c;
	int g=euclid(a,b,x,y);
	if(c%g!=0)
        fout<<0<<" "<<0<<"\n";
	else
		fout<<x*c/g<<" "<<y*c/g<<"\n";
}

int main()
{
	int t;
	fin>>t;
	while(t--)
		solve();
	return 0;
}