Cod sursa(job #2925533)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 15 octombrie 2022 17:11:40
Problema Algoritmul lui Euclid extins Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>

using namespace std;

long long gcd(long long a, long long b)
{
    if (a == 0)
        return b;
    if (b == 0)
        return a;

    long long rest;

    while (a % b)
    {
        rest = a % b;
        a = b;
        b = rest;
    }

    return b;
}

void euclidExtins(long long a, long long b, long long & d, long long & x, long long & y)
{
    if (b == 0)
    {
        d = a;
        x = 1;
        y = 1;
    }
    else
    {
        long long xAnt, yAnt;
        euclidExtins(b, a % b, d, xAnt, yAnt);
        x = yAnt;
        y = xAnt - a / b * yAnt;
    }
}

int main()
{
    ifstream in("euclid3.in");
    ofstream out("euclid3.out");

    int t;
    in >> t;

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

        if (a == 0 && b == 0)
        {
            out << 0 << ' ' << 0 << '\n';
        }
        else if (a == 0 && c % b == 0)
        {
            out << 0 << ' ' << c / b << '\n';
        }
        else if (b == 0 && c % a == 0)
        {
            out << c / a << ' ' << 0 << '\n';
        }
        else
        {
            long long d = gcd(a, b);

            if (c % d != 0)
            {
                out << 0 << ' ' << 0 << '\n';
            }
            else
            {
                long long x, y;
                euclidExtins(a, b, d, x, y);

                out << (x * c / d) % b << ' ' << (y * c / d) % a << '\n';
            }
        }
    }

    return 0;
}