Cod sursa(job #408919)

Utilizator SpiderManSimoiu Robert SpiderMan Data 3 martie 2010 12:40:11
Problema Ecuatie Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;

ifstream f("ecuatie.in");
ofstream g("ecuatie.out");

struct vector
{
    int p1,q1,p2,q2;
} q[1000];

int A,B,C,K,l;
double X1,X2;
double delta;
bool stop;

struct sorting1
{
    bool operator () (const vector& lhs , const vector& rhs)
    {
        if (lhs.p1 == rhs.p1)
            return lhs.q1 == rhs.q1;

        return lhs.p1 == rhs.p1;
    }
};
struct sorting
{
    bool operator () (const vector& lhs , const vector& rhs)
    {
        if (lhs.p1 == rhs.p1)
            return lhs.q1 < rhs.q1;

        return lhs.p1 < rhs.p1;
    }
};
inline int mod(int x,int y)
{
    return x-y*(x/y);
}
inline void calcul()
{
    int i,cnt;
    delta=B*B-(A*C<<2);
    /*for ( i = 1, cnt = (1<<16) ; cnt; cnt >>=1)
        if ((long long) (i + cnt) * (i + cnt) <= delta) i += cnt;*/
    if (sqrt(delta)==(int)sqrt(delta)) delta=(int)sqrt(delta);
    else stop=1;
    X1=(double)((-B-delta)/(A*2.0));
    X2=(double)((-B+delta)/(A*2.0));
}
inline void verf(int d)
{
    double a,b;
    a=-X1*d;
    b=-X2*(A/d);
    if ((a==int(a)) && (b==int(b)))
    {
        q[l].q1=int(a);
        q[l].p1=d;
        q[l].q2=int(b);
        q[l++].p2=A/d;
    }
    a=-X2*d;
    b=-X1*(A/d);
    if ((a==int(a)) && (b==int(b)))
    {
        q[l].q1=int(a);
        q[l].p1=d;
        q[l].q2=int(b);
        q[l++].p2=A/d;
    }
}
inline void divizor()
{
    int k=abs(A),i,cnt,d;
    for ( i = 1, cnt = (1<<16) ; cnt; cnt >>=1)
        if ((long long) (i + cnt) * (i + cnt) <= k) i += cnt;
    k=i;
    for ( d = 1; d <= k; d++)
        if (A%d==0)
        {
            verf(d);
            verf(-d);
            verf(A/d);
            verf(-A/d);
        }
}
int main()
{
    f>>A>>B>>C>>K;
    calcul();
    if (stop) g<<"-1";
    else
    {
        divizor();
        sort(q,q + l,sorting());
        l = unique(q, q + l ,sorting1()) - q;
        if (K>l) g<<"-1";
        else
        {
            g<<"(";
            if (q[K-1].p1==-1) g<<"-x";
            else if (q[K-1].p1==1) g<<"x";
            else g<<q[K-1].p1<<"x";
            if (q[K-1].q1>=0) g<<"+"<<q[K-1].q1<<")"<<"(";
            else g<<q[K-1].q1<<")"<<"(";
            if (q[K-1].p2==-1) g<<"-x";
            else if (q[K-1].p2==1) g<<"x";
            else g<<q[K-1].p2<<"x";
            if (q[K-1].q2>=0) g<<"+"<<q[K-1].q2<<")";
            else g<<q[K-1].q2<<")";
        }
    }
    return 0;
}