Cod sursa(job #3358169)

Utilizator nedeleavladNedelea Vlad-Matei nedeleavlad Data 15 iunie 2026 04:05:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <stdio.h>
// ALGORITMUL LUI EUCLID EXTINS - ecuatia a*x + b*y = c
// din curs stim ca pentru orice a, b exista x, y astfel incat   a*x + b*y = gcd(a, b)   <- asta e Lema lui Bezout

long long euclid_extins(long long a, long long b, long long *x, long long *y) {
    if (b == 0) {
        // cazul de baza: gcd(a, 0) = a si a*1 + 0*0 = a, deci x=1, y=0
        *x = 1;
        *y = 0;
        return a;
    }
    long long x1, y1;  // solutia pentru subproblema mai mica
    long long d = euclid_extins(b, a % b, &x1, &y1);
    // relatia de reconstructie din curs:  x = y1 si  y = x1 - (a/b) * y1
    *x = y1;
    *y = x1 - (a / b) * y1;
    return d;  // gcd-ul ramane acelasi pe tot parcursul recursiei
}

int main() {
    FILE *fin  = fopen("euclid3.in",  "r");
    FILE *fout = fopen("euclid3.out", "w");
    if (fin == NULL) {
        printf("nu gasesc fisierul euclid3.in\n");
        return 1;
    }
    int T;  // numarul de teste
    fscanf(fin, "%d", &T);
    int i;
    for (i = 0; i < T; i++) {
        long long a, b, c;
        fscanf(fin, "%lld %lld %lld", &a, &b, &c);
        long long x, y;
        long long d = euclid_extins(a, b, &x, &y);
        // acum avem: a*x + b*y = d (unde d = gcd(a,b))
        if (c % d != 0) {
            // din curs: daca c nu se divide cu d, nu exista solutie
            fprintf(fout, "0 0\n");
        } else {
            // inmultim toata ecuatia cu c/d ca sa trecem de la a*x + b*y = d la a*(x*c/d) + b*(y*c/d) = c
            long long cat = c / d;
            x = x * cat;
            y = y * cat;

            fprintf(fout, "%lld %lld\n", x, y);
        }
    }

    fclose(fin);
    fclose(fout);

    return 0;
}