Cod sursa(job #3136389)

Utilizator gal1l30Cristea Darius-Luca gal1l30 Data 6 iunie 2023 03:06:48
Problema Algoritmul lui Euclid extins Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <stdio.h>

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

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

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

    return cmmdc;
}

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

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

    scanf("%d", &T);

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

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

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

    return 0;
}