Cod sursa(job #2855005)

Utilizator Kawaiimeatball13Russu Mihaela Kawaiimeatball13 Data 21 februarie 2022 22:31:57
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int a_initial, b_initial, c;
int a[51], b[51];
int n;

void reducere_coef()
{
    a[0] = a_initial;
    b[0] = b_initial;

    while(b[n])
    {
        n++;
        a[n] = b[n - 1];
        b[n] = a[n - 1] % b[n - 1];
    }
}

void solutie()
{
    if(c % a[n])
    {
        fout << 0 << ' ' << 0;
        return ;
    }
    int x0, y0;
    int x, y;

    x0 = c / a[n];
    y0 = 0;

    while(n > 0)
    {
        n--;
        x = y0;
        y = x0 - a[n] / b[n] * y0;
        x0 = x;
        y0 = y;
    }

    fout << x0 << ' ' << y0;
}

void resetare()
{
    n = 0;
    for(int i = 0; i < 51; ++i)
        a[i] = b[i] = 0;
}

int main()
{
    int t;
    fin >> t;
    for(int i = 0; i < t; ++i)
    {
        fin >> a_initial >> b_initial >> c;
        reducere_coef();
        solutie();
        resetare();
        fout << '\n';
    }
    return 0;
}