Cod sursa(job #3236079)

Utilizator AndreasAntoniuAntoniu Andreas AndreasAntoniu Data 25 iunie 2024 23:19:51
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>

int euclid(int a, int b)
{
    if (!b)
    {
        return a;
    }
    return euclid(b, a % b);
}

void euclid_extins(int a, int b, int *x, int *y)
{
    int r0 = a, r1 = b, x0 = 1, x1 = 0, y0 = 0, y1 = 1;

    if (!b)
    {
        *x = x0;
        *y = y0;
    }
    else
    {
        while (r1)
        {
            int q = r0 / r1, aux;
            aux = r1;
            r1 = r0 - q * r1;
            r0 = aux;

            aux = x1;
            x1 = x0 - q * x1;
            x0 = aux;

            aux = y1;
            y1 = y0 - q * y1;
            y0 = aux;
        }
        *x = x0;
        *y = y0;
    }
}

int main()
{
    FILE *fin = fopen("euclid3.in", "rb");
    FILE *fout = fopen("euclid3.out", "wb");
    int n;
    fscanf(fin, "%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int a, b, c, d;
        fscanf(fin, "%d %d %d", &a, &b, &c);
        d = euclid(a, b);
        if (c % d != 0)
        {
            fprintf(fout, "%d %d\n", 0, 0);
        }
        else
        {
            int x, y;
            euclid_extins(a, b, &x, &y);
            fprintf(fout, "%d %d\n", x * (c / d), y * (c / d));
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}