Cod sursa(job #2227174)

Utilizator pinteastefanPintea Teodor Stefan pinteastefan Data 31 iulie 2018 13:45:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>

using namespace std;

void generatorSolution(long long a, long long b, long long &x, long long &y, long long &d)
{
    // ax + by = d
    // d este GCD(a,b)
    // facem o implementare recursiva pornind de la solutia de baza
    if (b == 0)
    {
        x = 1;
        y = 0;
        d = a;
        return ;
    }
    else // nu e necesar mereu, deoarece oricum executa operatiile daca if ul nu este atins
    {
        generatorSolution(b, a % b, x ,y, d);
        long long valueX = y;
        long long valueY = x - y * (a / b);
        x = valueX;
        y = valueY;

        // respecta demonstratia matematica
    }
}


int main() {

    ifstream inputfile("euclid3.in");
    ofstream outputfile("euclid3.out");

    int number;


    inputfile >> number;

    for ( int i = 1; i <= number; i ++)
    {
        long long a, b, c, x, y, d;

        inputfile >> a >> b >> c;

        generatorSolution(a, b, x, y, d);
        if (c % d)
            outputfile << "0 0\n";
        else
            outputfile << x * (c / d) << " " << y * (c / d) << "\n";

    }
    return 0;
}