Cod sursa(job #3134767)

Utilizator SimionAlexSimion Alex SimionAlex Data 30 mai 2023 20:17:03
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>

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

    int x1, y1;
    extended_euclidean_algorithm(b, a % b, &x1, &y1, answ);

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

FILE *file_in, *file_out;

int main()
{
    file_in = fopen("euclid3.in", "r");
    file_out = fopen("euclid3.out", "w");

    int T;
    fscanf(file_in, "%d", &T);

    for (int i = 1; i <= T; ++i)
    {
        int a, b, c;
        fscanf(file_in, "%d %d %d", &a, &b, &c);

        int x = 0, y = 0, answ = 0;
        extended_euclidean_algorithm(a, b, &x, &y, &answ);

        if (c % answ != 0)
            fprintf(file_out, "0 0\n");
        else
            fprintf(file_out, "%d %d\n", x * (c / answ), y * (c / answ));
    }

    fclose(file_in);
    fclose(file_out);
    return 0;
}