Cod sursa(job #3357408)

Utilizator Cosma_Laura_IoanaCosma Laura-Ioana Cosma_Laura_Ioana Data 9 iunie 2026 13:01:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>

long long absolut(long long x) // returneaza modulul numarului
{
    if (x < 0) return -x;
    else return x;
}

long long euclid_extins(long long a, long long b, long long *x, long long *y)
{
    if (b == 0)
    {
        *x = 1;
        *y = 0;
        return a;
    }

    long long x1, y1;
    long long d = euclid_extins(b, a % b, &x1, &y1);

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

    return d;
}

int main(void)
{
    FILE *fin = fopen("euclid3.in", "r");
    FILE *fout = fopen("euclid3.out", "w");
    if (fin == NULL)
    {
        printf("eroare deschidere fisier intrare\n");
        return 1;
    }
    if (fout == NULL)
    {
        printf("eroare deschidere fisier iesire\n");
        return 1;
    }

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

    for (int i = 0; i < T; i++)
    {
        long long a, b, c;
        fscanf(fin, "%lld %lld %lld", &a, &b, &c);

        long long x, y;

        if (a == 0 && b == 0)
        {
            fprintf(fout, "0 0\n");
            continue;
        }

        long long d = euclid_extins(absolut(a), absolut(b), &x, &y);

        if (c % d != 0)
            fprintf(fout, "0 0\n");
        else
        {
            // ajustez semnele coeficientilor daca numerele erau negative
            if (a < 0) x = -x;
            if (b < 0) y = -y;

            long long factor = c / d;
            x = x * factor;
            y = y * factor;

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

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