Cod sursa(job #3356800)

Utilizator Dumitru_SerbinaDumitru Serbina Dumitru_Serbina Data 4 iunie 2026 12:21:49
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

typedef struct {
    int64_t gcd;
    int64_t x;
    int64_t y;
} EuclidResult;

EuclidResult extended_gcd(int64_t a, int64_t b) {
    if (b == 0) {
        EuclidResult base = {a, 1, 0};
        return base;
    }
    EuclidResult next = extended_gcd(b, a % b);
    EuclidResult current;
    current.gcd = next.gcd;
    current.x = next.y;
    current.y = next.x - (a / b) * next.y;
    return current;
}

int main(void) {
    FILE *fin = fopen("euclid3.in", "r");
    if (fin == NULL) {
        perror(NULL);
        exit(1);
    }
    FILE *fout = fopen("euclid3.out", "w");
    if (fout == NULL) {
        perror(NULL);
        fclose(fin);
        exit(1);
    }

    int t;
    if (fscanf(fin, "%d", &t) == 1) {
        while (t--) {
            int64_t a, b, c;
            if (fscanf(fin, "%ld %ld %ld", &a, &b, &c) == 3) {
                EuclidResult res = extended_gcd(a, b);
                if (c % res.gcd != 0) {
                    fprintf(fout, "0 0\n");
                } else {
                    int64_t scale = c / res.gcd;
                    fprintf(fout, "%ld %ld\n", res.x * scale, res.y * scale);
                }
            }
        }
    }

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