Cod sursa(job #1648472)

Utilizator SmarandaMaria Pandele Smaranda Data 11 martie 2016 10:22:10
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>

using namespace std;

int A, B, C;

void read () {
    scanf ("%d%d%d", &A, &B, &C);
}

int euclid (int a, int b, int &x, int &y) {
    int x0, y0, d;

    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    else {
        d = euclid (b, a % b, x0, y0);
        x = y0;
        y = x0 - a / b * y0;
        return d;
    }
}

void solve () {
    int cmmdc, x, y;

    cmmdc = euclid (A, B, x, y);
    if (C % cmmdc) {
        printf ("0 0\n");
        return;
    }
    x = 1ll * x * C / cmmdc;
    y = 1ll * y * C / cmmdc;
    printf ("%d %d\n", x, y);
}

int main () {
    int T, t;

    freopen ("euclid3.in", "r", stdin);
    freopen ("euclid3.out", "w", stdout);

    scanf ("%d", &T);
    for (t = 1; t <= T; t ++) {
        read ();
        solve ();
    }
    return 0;
}