Cod sursa(job #2909452)

Utilizator crisan_007Crisan Cristian crisan_007 Data 13 iunie 2022 19:06:03
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
//Problema Algoritmul lui Euclid extins - Rezolvare C++: 100p -> infoarena.ro
//Stud. Cristian CRIȘAN - AC, CTI-RO, ANUL I

#include <iostream>
#include <fstream>

using namespace std;

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

int euclid_exstins(int &x, int &y, int a, int b) //algoritmul lui Euclid extins
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    else
    {
        int x1, y1;
        int t = euclid_exstins(x1, y1, b, a % b); //facem inca un pas al algoritmului
        x = y1;
        y = x1 - y1 * (a / b);
        return t;
    }
}

void solve(int n)
{
    int a, b, c, x = 0, y = 0, t;
    while(n --)
    {
        fin >> a >> b >> c;
        t = euclid_exstins(x, y, a, b);
        if(c % t) //daca c nu este divizibil cu t nu exista solutie
            fout << "0 0\n";
        else
            fout << x * (c / t) << ' ' << y * (c / t) << '\n';
    }
}

int main()
{
    int n;
    fin >> n;
    solve(n);
    return 0;
}