Cod sursa(job #3298952)

Utilizator tudorboscuTudor Boscu tudorboscu Data 3 iunie 2025 14:48:07
Problema Algoritmul lui Euclid extins Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

//este cumva o varianta mai generala a inversului modular, aici dupa egal nu o sa mai fie 1, o sa fie o necunoscuta 'c'

// void euclid_extins(int64_t a, int64_t b, int64_t *res, int64_t *x, int64_t *y)
// {
//     if (b == 0){   // in cazul asta avem a * 1 + 0 = c
//         *x = 1;
//         *y = 0;
//         *res = a;
//         return;
//     }
//     else{ //rotim a si b;
//         int64_t x_aux, y_aux;
//         euclid_extins(b, a % b, res, &x_aux, &y_aux);

//         *x = y_aux;
//         *y = x_aux - ((a / b) * y_aux);
//     }

// }

int euclid_extins(int a, int b, int *x, int *y)
{
    if (b == 0){   // in cazul asta avem a * 1 + 0 = c
        *x = 1;
        *y = 0;
        return a;
    }
    else{ //rotim a si b;
        int x_aux, y_aux;
        int res;
        res = euclid_extins(b, a % b, &x_aux, &y_aux);

        *x = y_aux;
        *y = x_aux - ((a / b) * y_aux);
        return res;
    }

}

int main(void)
{
    FILE *fin = fopen("euclid3.in", "r");
    FILE *fout = fopen("euclid3.out", "w");

    int T; // intre 1 si 100
    fscanf(fin, "%d", &T);
    // scanf("%d", &T);
    // getchar();

    for(uint16_t i = 0; i < T; i++)
    {
        int a, b, c;
        // scanf("%d %d %d", &a, &b, &c);
        // getchar();
        fscanf(fin, "%d %d %d", &a, &b, &c);
        
        int x, y;
        int res;
        res = euclid_extins(a, b, &x, &y);   //obtinem res si tratam in functie de inputul de lla c
        
        if (res < 0){   // ca sa nu avem probleme cu semnele negative
            res = -res;
            x = x;
            y = y;
        }

        if (c % res){
            // printf("0 0\n");
            fprintf(fout, "0 0\n");
        }
        else{
            x = x * c / res;
            y = y * c / res;

            // printf("%d %d\n", x, y);
            fprintf(fout, "%d %d\n", x, y);
        }
        // fprintf(fout, "%ld %ld\n", x, y);
    }


    fclose(fin);
    fclose(fout);
    return 0;
}