Cod sursa(job #2440836)

Utilizator katanau26@yahoo.comIonut Barbu [email protected] Data 19 iulie 2019 14:24:21
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>

using namespace std;

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

void gcdExtRec(int a, int b, int &d, int&x, int &y)
{
    if(b == 0)
        d = a, x = 1, y = 0;
    else
    {
        int x0, y0;
        gcdExtRec(b, a % b, d, x0, y0);
        x = y0;
        y = x0 - a / b * y0;
    }
}

void gcdExt(int a, int b, int &d, int &x, int &y)
{
    int x1, y1, r, q;

    x = 1, y = 0;
    x1 = 0, y1 = 1;

    while (b)
    {
        q = a / b;

        r = a - b * q;              //r = a % b, a = b, b = r
        a = b;
        b = r;

        r = x - x1 * q;             //r = x % x1, x = x1, x1 = r
        x = x1;
        x1 = r;

        r = y - y1 * q;             //r = y % y1, y = y1, y1 = r
        y = y1;
        y1 = r;
    }

    d = a;    
}

int main()
{
    int a, b, c, d, x, y, T;

    fin >> T;
    for (size_t i = 0; i < T; i++)
    {
        fin >> a >> b >> c;
        gcdExt(a, b, d, x, y);
        if(c % d)
            fout << "0 0 \n";
        else
            fout << x * (c / d) << " " << y * (c / d) << "\n";        
    }

    return 0;
}