Cod sursa(job #3298866)

Utilizator blnsara_10Sara Balanescu blnsara_10 Data 2 iunie 2025 19:52:13
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
//https://infoarena.ro/problema/euclid3
#define LL long long

LL euclid(LL a, LL b, LL *x, LL *y) {
    //base case
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    LL x1, y1;
    LL d = euclid(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 -(a/b)*y1;
    return d;
}

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

    int t;
    fscanf(in, "%d", &t);

    while (t--)
    {
        LL a, b, c, x, y;
        fscanf(in, "%lld %lld %lld", &a, &b, &c);

        LL d = euclid(a, b, &x, &y);
        if (c % d != 0)
            fprintf(out, "0 0\n");
        else {
            x *= c / d;
            y *= c / d;
            fprintf(out, "%lld %lld\n", x, y);
        }
    }

    fclose(in);
    fclose(out);
    return 0;
}