Cod sursa(job #3234621)

Utilizator alexxiacrisanCrisan Maria - Alexia alexxiacrisan Data 10 iunie 2024 18:21:59
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>

using namespace std;

struct eucl 
{
    int d, x, y;
};

eucl euclidExtins(int a, int b) 
{
    if (b == 0) 
    {
        eucl ret;
        ret.d = a;
        ret.x = 1;
        ret.y = 0;
        return ret;
    } 
    else 
    {
        eucl var = euclidExtins(b, a % b);
        eucl ret;
        ret.d = var.d;
        ret.x = var.y;
        ret.y = var.x - (a / b) * var.y;
        return ret;
    }
}

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

    int T;
    fin >> T;

    while (T--) 
    {
        int a, b, c;
        fin >> a >> b >> c;

        eucl result = euclidExtins(abs(a), abs(b));

        if (c % result.d != 0) 
            fout << "0 0" << endl;
        else 
        {
            int x = result.x * (c / result.d);
            int y = result.y * (c / result.d);

            if (a < 0) x = -x;
            if (b < 0) y = -y;

            fout << x << " " << y << endl;
        }
    }

    fin.close();
    fout.close();

    return 0;
}