Cod sursa(job #3357770)

Utilizator Ilie_Andra_MariaIlie Andra Maria Ilie_Andra_Maria Data 13 iunie 2026 14:33:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>

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

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

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

    return cmmdc;
}

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

    if (fin == NULL || fout == NULL) {
        return 0;
    }

    long t;
    if (fscanf(fin, "%ld", &t) != 1) {
        fclose(fin);
        fclose(fout);
        return 0;
    }

    while (t > 0)
    {
        long a, b, c;
        fscanf(fin, "%ld %ld %ld", &a, &b, &c);

        long x0, y0;
        long d = euclid_extins(a, b, &x0, &y0);

        if (c % d != 0)
        {
            fprintf(fout, "0 0\n");
        }
        else
        {
            long x_final = x0 * (c / d);
            long y_final = y0 * (c / d);

            fprintf(fout, "%ld %ld\n", x_final, y_final);
        }

        t--;
    }

    fclose(fin);
    fclose(fout);

    return 0;
}