Cod sursa(job #2772898)

Utilizator guzgandemunteIonescu Laura guzgandemunte Data 3 septembrie 2021 11:59:10
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

struct nr{int unu, doi;}a, b, r;

int t, m, n, p;

int val(nr a)
{
    return m * a.unu + n * a.doi;
}

int main ()
{
    fin >> t;

    for (int contor = 1; contor <= t; contor++)
    {
        fin >> m >> n >> p;
        if (m == 0) fout << 0 << " " << n << endl;
        else if (n == 0) fout << m << " " << 0 << endl;
        else if (p == 0) fout << 0 << " " << 0 << endl;
        else
        {
            a.unu = 1, a.doi = 0;
            b.unu = 0, b.doi = 1;
            r.unu = a.unu - (val(a) / val(b)) * b.unu;
            r.doi = a.doi - (val(a) / val(b)) * b.doi;

            while (val(r))
            {
                a.unu = b.unu, a.doi = b.doi;
                b.unu = r.unu, b.doi = r.doi;

                r.unu = a.unu - (val(a) / val(b)) * b.unu;
                r.doi = a.doi - (val(a) / val(b)) * b.doi;
            }

            if (p % val(b))
                fout << 0 << " " << 0 << endl;
            else
                fout << b.unu * (p / val(b)) << " " << b.doi * (p / val(b)) << endl;
        }
    }

    fin.close();
    fout.close();
    return 0;
}