Cod sursa(job #1803467)

Utilizator rangalIstrate Sebastian rangal Data 11 noiembrie 2016 15:13:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <cstdio>
#include <cassert>
#define infile "euclid3.in"
#define outfile "euclid3.out"
#define NMAX 1000000000

using namespace std;

inline int gcd( int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }

    int x0, y0, d;
    d = gcd( b, a%b, x0, y0);

    x = y0;
    y = x0 - (a / b) * y0;
    return d;
}

// return a - determina cmmdc(a,b) initiali. Se repeta returnarea lor prin variabila d.
// intre timp se calculeaza x si y in functie de x0,y0.

int main()
{
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    int T;

    for (scanf("%d", &T), assert( T <= 100 ); T; T--)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        assert( -NMAX <= a && a <= NMAX );
        assert( -NMAX <= b && b <= NMAX );
        assert( - (NMAX*2) <= c && c <= (NMAX*2) && c != 0 );

        int d, x, y;

        d = gcd( a, b, x, y);

    // x,y reprezinta solutiile ecuatiei pentru a*x + b*y = d,(d fiind cmmdc(a,b) initial)
    // Daca c se imparte exact la d , se amplifica ecuatia cu c/d , si cum a,b sunt constante
    // coeficientii finali ai numerelor a si b sunt x*(c/d) , respectiv y*(c/d).
    //      Daca nu, coeficientii x,y nu aduc solutie in multimea Z.
        //printf("x= %d, y= %d, cmmdc(a,b)= %d\n",x,y,d);

        if (c%d!=0)
            printf("0 0\n");
        else
            printf("%d %d\n", x * (c / d), y * (c / d));
    }

    return 0;
}