Cod sursa(job #2476580)

Utilizator andreigaliAndrei Galitianu andreigali Data 19 octombrie 2019 09:46:17
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>



int eulcid_eXt(int a, int b, int c, int &x, int &y)

{

    int q[100], x0, y0, r, p=0;


    while(b != 0)

    {

        r = a%b;

        q[++p] = a/b;

        a=b;

        b=r;

    }

    if(c%a)

        return 0;


    x0 = c/a;

    x = x0;

    y0 = 0;

    y = y0;


    while(p>0)

    {

        x= y0;

        y = x0 - (q[p--]*y0);

        x0 = x;

        y0 = y;

    }

    return 1;

}

int main()

{

    FILE *f = fopen("euclid3.in", "r");

    FILE *g = fopen("euclid3.out", "w");


    int t, a, b, c, q[100], p=1, x, y;

    fscanf(f, "%d", &t);

    for(int i=0; i<t; i++)
    {
        fscanf(f, "%d%d%d", &a, &b, &c);
        if(eulcid_eXt(a, b, c, x, y) == 0)

            fprintf(g, "0 0\n");

        else

            fprintf(g, "%d %d\n", x, y);

    }

    return 0;

}