Cod sursa(job #3136390)

Utilizator gal1l30Cristea Darius-Luca gal1l30 Data 6 iunie 2023 03:22:49
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.95 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);

        assert( -1000000000 <= A && A <= 1000000000 );
        assert( -1000000000 <= B && B <= 1000000000 );
        assert( -2000000000 <= C && C <= 2000000000 && C != 0 );

        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;
}