Cod sursa(job #2462397)

Utilizator pslaPislariu Alexandru psla Data 27 septembrie 2019 11:26:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>

using namespace std;

int gcd_extins(int a, int b, int &x, int &y, int &d)
{/*Algoritmul rezolva ecuatia a*x + b*y = d, unde d este cmmdc(a,b)
Date de intrare: a,b coeficienti cunoscuti, numere intregi
Date de iesire: x,y necunoscutele ecuatiei
*/
    if(b==0)
    {/*primul apel*/
        d = a;
        x = 1;
        y = 0;
    }
    else
    {
/*necunoscutele apelului precedent*/
    int x0=0, y0=0;
    gcd_extins(b,a%b,x0,y0,d);

/*necunoscutele apelului curent, dependenta se demonstreaza prin calcul matematic*/
    x = y0;
    y = x0 - (a/b)*y0;
    }
}

void solve()
{ifstream in("euclid3.in");
ofstream out("euclid3.out");
    int nT;
    in>>nT;

    for(int i=0; i<nT; i++)
    {
        int a,b,c;
        in>>a>>b>>c;

    /*Se cere rezolvarea ecuatiei a*x + b*y = c, a,b,c,x,y sunt numere intregi.
    Din algoritmul lui Euclid extins => a*x + b*y = (a,b) => ecuatia se poate rezolva <=> c este multiplu de (a,b)
    */
        int x=0, y=0, d=0;
        gcd_extins(a,b,x,y,d);

        if(c%d==0)/*se poate rezolva*/
            out<<(c/d)*x<<" "<<(c/d)*y<<'\n';
        else
            out<<0<<" "<<0<<'\n';
    }

in.close();
out.close();
}
int main()
{
    solve();
    return 0;
}