Cod sursa(job #3136391)

Utilizator gal1l30Cristea Darius-Luca gal1l30 Data 6 iunie 2023 03:23:51
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>
#include <assert.h>

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

    int x1, y1;
    int cmmdc = euclidExtended(b % a, a, &x1, &y1);

    *x = y1 - (b / a) * x1;
    *y = x1;

    return cmmdc;
}

int main() {
     int T, A, B, C;
     int finalCMMDC;

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

    scanf("%d", &T);

    for (int index = 1; index <= T; ++index) {
        scanf("%d %d %d", &A, &B, &C);
        

        int X, Y;
        finalCMMDC = euclidExtended(A, B, &X, &Y);

        if (C % finalCMMDC) {
            printf("0 0\n");
        } else {
            printf("%d %d\n", X * (C / finalCMMDC), Y * (C / finalCMMDC));
        }
    }

    return 0;
}