Cod sursa(job #1160641)

Utilizator cbanu96Banu Cristian cbanu96 Data 30 martie 2014 18:01:54
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>

using namespace std;

#define FILEIN "euclid3.in"
#define FILEOUT "euclid3.out"

void euclidext(int a, int b, int &d, int &x, int &y) {
    if ( b == 0 ) {
        // a * 1 + b * 0 = d
        d = a;
        x = 1;
        y = 0;

        return;
    }

    int _x, _y;
    euclidext(b, a % b, d, _x, _y);
    x = _y;
    y = _x - (a / b) * _y;
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    int T;
    for (scanf("%d", &T); T; T--) {
        int a, b, c, x, y, d;
        scanf("%d %d %d", &a, &b, &c);
        euclidext(a, b, d, x, y);

        if (c % d) {
            printf("0 0\n");
        } else {
            printf("%d %d\n", x * (c / d) , y * (c / d));
        }
    }

    return 0;
}