Cod sursa(job #2203579)

Utilizator Menage_a_011UPB Cheseli Neatu Popescu Menage_a_011 Data 12 mai 2018 18:08:23
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
// https://goo.gl/fBmFxu
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;

#define NMAX        100009
#define MMAX        200009
#define kInf        (1 << 30)
#define kInfLL      (1LL << 60)
#define kMod        666013
#define edge pair<int, int>
#define x first
#define y second

#define USE_FILES "MLC"

#ifdef USE_FILES
#define cin fin
#define cout fout
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
#endif

// number of tests from "in"
int test_cnt = 1;
void clean_test();

// your global variables are here
template<typename T>
T gcd(T a, T b, T &x, T &y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }

    T x0, y0;
    T d = gcd(b, a % b, x0, y0);

    x = y0;
    y = x0 - (a / b) * y0;

    return d;
}

// your solution is here
void solve() {
    long long a, b, c;
    cin >> a >> b >> c;

    long long x, y;
    long long d = gcd(a, b, x, y);
    if (c % d != 0) {
        x = y = 0;
    } else {
        x *= (c / d);
        y *= (c / d);
    }
    cout << x << " " << y << "\n";

    if (test_cnt > 0) {
        clean_test();
    }
}


void clean_test() {
    // clean if needed
}

int main() {
    cin >> test_cnt;
    while (test_cnt--) {
        solve();
    }

    return 0;
}