Cod sursa(job #3292225)

Utilizator unomMirel Costel unom Data 7 aprilie 2025 16:27:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>

using namespace std;

struct el
{
    int gcd, x, y;
};

ifstream in("euclid3.in");
ofstream out("euclid3.out");
int t;
int a, b, c;

el euclid(int a, int b)
{
    if(b == 0)
    {
        return {a, 1, 0};
    }
    else
    {
        el func = euclid(b, a % b);

        int x = func.y;
        int y = func.x - (a / b) * func.y;

        return {func.gcd, x, y};
    }
}

int main()
{
    in>>t;

    while(t--)
    {
        in>>a>>b>>c;

        el euc = euclid(a, b);

        if(c % euc.gcd != 0)
        {
            out<<"0 0\n";
        }
        else
        {
            int k = c / euc.gcd;

            out<<euc.x * k<<" "<<euc.y * k<<'\n';
        }
    }
    return 0;
}