Cod sursa(job #584028)

Utilizator caen1c a e n caen1 Data 23 aprilie 2011 17:15:14
Problema Algoritmul lui Euclid extins Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.76 kb
/**
 * user: caen1
 * file: infoarena/euclid3.c
 * date: 23 apr 2011
**/
#include <stdio.h>

#define IN "euclid3.in"
#define OUT "euclid3.out"

long euclid(long, long, long *, long *);

int main(void) {

    int n;
    long a, b, c, d, x, y;

    (void) freopen(IN, "r", stdin);
    (void) freopen(OUT, "w", stdout);

    (void) scanf("%d", &n);

    while(n--) {

        (void) scanf("%ld %ld %ld", &a, &b, &c);

        d = euclid(a, b, &x, &y);

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

    return 0;
}

long euclid(long a, long b, long *x, long *y) {

    long x0, y0, d;

    if(!b) {
        
        *x = 1, *y = 0;
        return a;
    }

    d = euclid(b, a % b, &x0, &y0);
    *x = y0, *y = x0 - (a / b) * y0;

    return d;
}