Cod sursa(job #1266689)

Utilizator codebreaker24Tivadar Ionut codebreaker24 Data 18 noiembrie 2014 23:50:33
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
// Program de aplicar EuclidExtin
# include <fstream>
using namespace std;

int euclid_ext (int *x, int *y, int a, int b);




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




int main ()
{
    int n;
    int a, b, d;
    int x, y;
    int cmmdc;

    fin >> n;
    for(int i=0; i<n;i++)
    {
        fin >> a >> b >> d;

        cmmdc = euclid_ext(&x, &y, a, b);

        if (d%cmmdc!= 0)
        fout << 0 << ' '<<  0 << '\n';
        else
        {
            fout << x*(d/cmmdc) <<' '<< y*(d/cmmdc) << '\n';


        }

    }


    return 0;

}



int euclid_ext (int *x, int *y, int a, int b)
{
       if (b==0)
       {
           *x = 1;
           *y = 0;
           return a;
       }
       else
        {
            int x0, y0,c;
         c =  euclid_ext(&x0, &y0, b, a%b);
         *x = y0;
         *y = x0 - int(a/b)*y0;
         return c;

        }
}