Cod sursa(job #3357081)

Utilizator SimionescuGabrielSimionescu Gabriel SimionescuGabriel Data 5 iunie 2026 20:11:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>

long long cmmdc(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 c = cmmdc(b, a % b, &x1, &y1);

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

    return c;
}

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

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

    while (t--)
    {
        long long a, b, c;
        fscanf(fin, "%lld %lld %lld", &a, &b, &c);

        long long x, y;
        long long cmm = cmmdc(a, b, &x, &y);

        if (c % cmm != 0)
            fprintf(fout, "0 0\n");
        else
        {
            long long k = c / cmm;
            fprintf(fout, "%lld %lld\n", x * k, y * k);
        }
    }

    fclose(fin);
    fclose(fout);

    return 0;
}