Cod sursa(job #3358130)

Utilizator Lupu_Mirabela_DianaLupu Mirabela Diana Lupu_Mirabela_Diana Data 14 iunie 2026 21:00:02
Problema Algoritmul lui Euclid extins Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>

long long euclid(long long a, long long b, long long *x, long long *y)
{
    if (b == 0)
    {
        *x = 1;
        *y = 0;

        if (a < 0)
            return -a;

        return a;
    }

    long long x1, y1;

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

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

    return d;
}

int main()
{
    FILE *in, *out;

    int T;
    long long a, b, c;
    long long x, y;
    long long d;

    in = fopen("euclid3.in", "r");
    out = fopen("euclid3.out", "w");

    fscanf(in, "%d", &T);

    while (T--)
    {
        fscanf(in, "%lld %lld %lld", &a, &b, &c);

        d = euclid(a, b, &x, &y);

        if (c % d != 0)
        {
            fprintf(out, "0 0\n");
            continue;
        }

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

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

    fclose(in);
    fclose(out);

    return 0;
}