Cod sursa(job #3358129)

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

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

    long long x1, y1;

    euclid(b, a % b, &x1, &y1);

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

long long cmmdc(long long a, long long b)
{
    while (b)
    {
        long long r = a % b;
        a = b;
        b = r;
    }

    return a >= 0 ? a : -a;
}

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 = cmmdc(a, b);

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

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

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

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

    fclose(in);
    fclose(out);

    return 0;
}