Cod sursa(job #1479285)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 30 august 2015 22:50:33
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <tuple>

using namespace std;

#define inFile "euclid3.in"
#define outFile "euclid3.out"

ifstream in(inFile);
ofstream out(outFile);

tuple < int, int, int > gcd(int a, int b) {
    if(a % b == 0) return make_tuple(b, 0, 1);
    tuple < int, int, int > gcdNext = gcd(b, a % b);
    return make_tuple(get<0>(gcdNext),
                      get<2>(gcdNext),
                      get<1>(gcdNext) - (a / b) * get<2>(gcdNext));
}

int main() {
    int testCase, a, b, c, x, y, d;
    tuple < int, int, int > gcdRet;

    in >> testCase;
    while(testCase--) {
        in >> a >> b >> c;
        gcdRet = gcd(a, b);
        d = get<0>(gcdRet);
        x = get<1>(gcdRet);
        y = get<2>(gcdRet);


        //out << a << " " << b << " " << d << " " << x << " " << y << "\n";
        if(c % d == 0) {
            x *= (c / d);
            y *= (c / d);
        }
        else {
            x = 0;
            y = 0;
        }
        out << x << " " << y << "\n";
    }

    return 0;
}