Cod sursa(job #1989069)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 5 iunie 2017 18:49:25
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <utility>
#include <algorithm>
#include <tuple>


std::tuple<int, int, int> gcd(int a, int b) {
    int x0(1), x1(0), y0(0), y1(1);

    int divRes, aux;

    while (b) {
        divRes = a / b;
        aux = b;
        b = a % b;
        a = aux;

        aux = x1;
        x1 = x0 - divRes * x1;
        x0 = aux;

        aux = y1;
        y1 = y0 - divRes * y1;
        y0 = aux;
    }

    return std::make_tuple(a, x0, y0);
}


int main() {
    std::ifstream inFile("euclid3.in");
    std::ofstream outFile("euclid3.out");


    int nV, a, b, c;

    inFile >> nV;

    for (int i = 0; i < nV; i++) {
        inFile >> a >> b >> c;

        auto res = gcd(a, b);

        if (c % std::get<2>(res)) {
            outFile << 0 << ' ' << 0 << std::endl;
        } else {
            outFile << std::get<0>(res) * (c / std::get<2>(res)) << ' ' <<
                std::get<1>(res) * (c / std::get<2>(res)) << std::endl;
        }

    }

    outFile.close();
    inFile.close();
    return 0;
}