Cod sursa(job #546284)

Utilizator DraStiKDragos Oprica DraStiK Data 4 martie 2011 18:50:11
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <algorithm>
using namespace std;

#define LIM 1005

int x1,x2,P,K;

void read ()
{
    scanf ("%d%d%d%d",&x1,&x2,&P,&K);
}

inline int extended_gcd (int a,int b,int &x,int &y)
{
    int d,x0,y0;

    if (!b)
    {
        x=1; y=0;

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

    return d;
}

int get_solution (int &d1,int &d2)
{
    int d,i;

    d=extended_gcd (x1,x2,d1,d2);
    if (!(P%d))
    {
        for (i=0; d1+d2<K*d/P && i<=LIM; ++i)
        {
            d1+=x2/d; d2-=x1/d;
        }
        d1=d1*(P/d);
        d2=d2*(P/d);

        return 1;
    }

    return 0;
}

void solve ()
{
    int d1,d2,p1,p2,n1,n2;

    if (get_solution (d1,d2))
    {
        if (K+d1+d2<0 || (K+d1+d2)&1)
            printf ("NU");
        else
            for (p1=0; p1<=((K+d1+d2)>>1); ++p1)
            {
                p2=((K+d1+d2)>>1)-p1;
                n1=p1-d1; n2=p2-d2;

                if (p1>=0 && p2>=0 && n1>=0 && n2>=0)
                {
                    printf ("DA\n%d %d %d %d",p1,n1,p2,n2);
                    break ;
                }
            }

    }
    else
        printf ("NU");
}

int main ()
{
    freopen ("jjoe.in","r",stdin);
    freopen ("jjoe.out","w",stdout);

    read ();
    solve ();

    return 0;
}