Cod sursa(job #721737)

Utilizator sana1987Laurentiu Dascalu sana1987 Data 24 martie 2012 00:50:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>

int euclide(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    
    int x0, y0, result = euclide(b, a % b, &x0, &y0);
    *x = y0;
    *y = x0 - (a/b) * y0;
    return result;
}

int main() {
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
        
    int T;
    int i;
    int a, b, c;
    int x, y;

    scanf("%d", &T);
    for (i=0;i<T;i++) {
        scanf("%d %d %d", &a, &b, &c);
        int d = euclide(a, b, &x, &y);
        if (c % d)
            printf("0 0\n");
        else
            printf("%d %d\n", x *(c/d), y * (c/d));
    }

    return 0;
}