Cod sursa(job #2605887)

Utilizator KPP17Popescu Paul KPP17 Data 26 aprilie 2020 10:37:35
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.55 kb
#define fisier "ULTRA"
#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");

const int aleatoriu = 0;

void _sol(int a, int b, int c, int& x, int& y)
{
    if (!a && !b)
    {
        x = y = 0;
        return;
    }

    if (!a)
    {
        if (c % b)
            x = y = 0;
        else
            x = aleatoriu, y = c / b;
        return;
    }

    if (!b)
    {
        _sol(b, a, c, y, x);
        return;
    }

    _sol(b, a % b, c, y, x);
    y -= (a/b)*x;
}

void sol(int a, int b, int c, int& x, int& y)
{
    if (a < b)
        _sol(b, a, c, y, x);
    else
        _sol(a, b, c, x, y);
}

int main()
{
    int t; in >> t;

    while (t--)
    {
        int a, b, c, x = 0, y = 0;

        in >> a >> b >> c;
        sol(a, b, c, x, y);
        out << x << ' ' << y << '\n';
    }
}



/*
24x + 15y = 147

24*6 = 144
15*0 = 0

adaugam un 24 si scadem 15 pana cand avem un numar mai mic decat 15. obtinem un net de +9
24 % 15 = 9
merge de 0 ori

facem ce am facut mai sus si -scadem- numarul mai mic decat 15 (care este 9)
adica din x scadem 1
si la y adaugam 24 / 15 care este 1
daca punem un 15, si scadem un 9 (adica scoatem un 24 si punem un 15). obtinem un net de +6
15 % (24 % 15) = 6
merge de 0 ori
defapt putem face recursia asta pana la infinit pentru ca operandul din dreapta mereu va scadea
ia sa vedem daca facem numai cu 15
15 % (15 % (24 % 15)) = 15 % 6 = 3
15 % (15 % (15 % (24 % 15))) = 15 % 3 = 0
in ritmul asta nu putem ajunge decat pana la net de +3

algoritmul pentru net minim pozitiv obtinut este:
ia un 15, pune un 24 => net de +9
pune un 15, ia un 24, pune un 15 => net de +6
(fa asta de 2 ori: (ia un 15, pune un 24, ia un 15)), pune un 15 => net de +3

ia sa vedem cu 24

24 % (24 % 15) = 6
24 % (24 % (24 % 15)) = 0

tot nu ajungem nicaieri, si totusi solutie exista

solutia este sa punem 33 de 24 si sa luam 43 de 15

33*24 - 43*15 = 147

sa vedem ce se intampla:
se adauga 6 de 24 pentru a ajunge la 144
se adauga odata 24, se ia un 15 si se ajunge la ...

ma ia stai putin ce fac aici

ce ar fi sa fac un algoritm recursiv

sol(a, b, c) = (x, y) pereche de doi intregi solutie

sol(a, b, c) poate sa fie egala cu (c/a, 0) + sol(a, b, c - c/a)
// unde adunarea unei perechi (n, m) + (e, f) inseamna perechea (n+e, m+f)
sau poate sa fie egala cu (0, c/b) + sol(a, b, c - c/b)
sau poate sa fie egala cu {
    p = sol(b, a % b, c)
    x = p.y
    y = p.x - (a/b)*p.y
    return (x, y)
}

o sa o scriu intr-un program
*/