Cod sursa(job #2140391)

Utilizator 24601Dan Ban 24601 Data 23 februarie 2018 13:47:07
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>

struct euclid {
    int x, y, d;
};

static struct euclid cmmdc(int a, int b)
{
    struct euclid e;
    int x, y;

    if (b == 0) {
        e.x = 1;
        e.y = 0;
        e.d = a;
    } else {
        e = cmmdc(b, a % b);
        x = e.y;
        y = e.x - (a / b) * e.y;
        e.x = x;
        e.y = y;
    }

    return e;
}

int main(void)
{
    int t, a, b, c;
    struct euclid e;

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

    scanf("%d", &t);

    while (t--) {
        scanf("%d %d %d", &a, &b, &c);
        e = cmmdc(a, b);

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

    return 0;
}