Cod sursa(job #425526)

Utilizator DraStiKDragos Oprica DraStiK Data 25 martie 2010 20:36:21
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <algorithm>
#include <cmath>
using namespace std;

#define DIM 1000005

struct ecuatie {long long p1,p2,q1,q2;} v[DIM];
long long n,m,a,b,c,k,delta;
long double x1,x2;

inline void check (long long val)
{
    long double p,q;

    p=-x1*val;
    q=-x2*(a/val);
    if (p==(long long)p && q==(long long)q)
    {
        v[n].p1=val;
        v[n].p2=a/val;
        v[n].q1=(long long)p;
        v[n].q2=(long long)q;
        ++n;
    }
    p=-x2*val;
    q=-x1*(a/val);
    if (p==(long long)p && q==(long long)q)
    {
        v[n].p1=val;
        v[n].p2=a/val;
        v[n].q1=(long long)p;
        v[n].q2=(long long)q;
        ++n;
    }
}

struct cmp
{
    bool operator () (const ecuatie &a,const ecuatie &b)
    {
        return a.p1<b.p1 || (a.p1==b.p1 && a.q1<b.q1);
    }
};

struct rem
{
    bool operator () (const ecuatie &a,const ecuatie &b)
    {
        return a.p1==b.p1 && a.q1==b.q1 && a.p2==b.p2 && a.q2==b.q2;
    }
};

void print ()
{
    printf ("(");
    if (v[k].p1==-1)
        printf ("-x");
    else if (v[k].p1==1)
        printf ("x");
    else
        printf ("%lldx",v[k].p1);
    if (v[k].q1>0)
        printf ("+%lld)(",v[k].q1);
    else
        printf ("%lld)(",v[k].q1);
    if (v[k].p2==-1)
        printf ("-x");
    else if (v[k].p2==1)
        printf ("x");
    else
        printf ("%lldx",v[k].p2);
    if (v[k].q2>0)
        printf ("+%lld)",v[k].q2);
    else
        printf ("%lld)",v[k].q2);
}

void solve ()
{
    int i;

    delta=b*b-4*a*c;
    if (sqrt (delta)!=(long long)sqrt (delta))
    {
        printf ("-1");
        return ;
    }
    delta=(long long)sqrt (delta);
    x1=(long double)(-b+delta)/(2*a);
    x2=(long double)(-b-delta)/(2*a);
    for (i=1; i*i<=abs (a); ++i)
        if (a%i==0)
        {
            check (i);
            check (-i);
            check (a/i);
            check (-a/i);
        }
    sort (v,v+n,cmp ());
    m=unique (v,v+n,rem ())-v;
    if (k>m)
    {
        printf ("-1");
        return ;
    }
    --k;
    print ();
}

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

    scanf ("%lld%lld%lld%lld",&a,&b,&c,&k);
    solve ();

    return 0;
}