Cod sursa(job #1009924)

Utilizator sziliMandici Szilard szili Data 13 octombrie 2013 23:50:12
Problema Algoritmul lui Euclid extins Scor 60
Compilator c Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>
#include <stdlib.h>



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

        return d;
    }
}


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

    int t, a, b, c, d, x,y;

    scanf("%d", &t);

    for (int i=0; i<t; i++) {
        scanf("%d %d %d", &a, &b, &c);

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

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


    return 0;
}