Cod sursa(job #111813)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 1 decembrie 2007 22:38:10
Problema Ecuatie Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define f first
#define s second

long long A, B, C, K;
long long i, nrd;
long long a, b, c, e, delta;
double x, y;
vector<pair<long long,long long> > d;
vector<pair<pair<long long,long long>, pair<long long,long long> > > sol;

int main()
{
	freopen("ecuatie.in", "r", stdin);
	freopen("ecuatie.out", "w", stdout);
	scanf("%lld%lld%lld%lld", &A, &B, &C, &K);
	long long delta = B*B-4*A*C;
        a = sqrt(delta);
	if ((delta<0)||(a*a<delta)) {printf("-1\n"); return 0; }

		double x1 = (-B-sqrt(delta))/(2*A);
		double x2 = (-B+sqrt(delta))/(2*A);
		for (i = 2; i*i <= A; i++) 
		    if (A%i==0)
                    {
                        d.pb(mp(i,A/i));
                        if ((i*i)!=A) d.pb(mp(A/i,i)), d.pb(mp(-A/i,-i));
                        d.pb(mp(-i,-A/i));
                    }
                d.pb(mp(A,1));
                if (A!=1) d.pb(mp(1,A)), d.pb(mp(-1,-A));
                d.pb(mp(-A,-1));
		sort(d.begin(),d.end());

                nrd = d.size();

                for (i = 0; i < nrd; i++)
                {
                     a = -x1*d[i].f;
                     x = -x1*(double)d[i].f;
                     b = -x2*d[i].s;
                     y = -x2*(double)d[i].s;
                     if (x==a&&y==b)
                        sol.pb(mp(mp(d[i].f,a),mp(d[i].s,b)));

                     a = -x2*d[i].f;
                     x = -x2*(double)d[i].f;
                     b = -x1*d[i].s;
                     y = -x1*(double)d[i].s;
                     if (x==a&&y==b)
                        //if (x1!=x2)
                           sol.pb(mp(mp(d[i].f,a),mp(d[i].s,b)));
                }

                sort(sol.begin(),sol.end());

                nrd = sol.size();

		if (K>nrd) { printf("-1\n"); return 0; }

                /*for (i = 0; i < nrd; i++)
                    printf("%lld %lld %lld %lld\n", sol[i].f.f, sol[i].f.s, sol[i].s.f, sol[i].s.s);*/

                K--;
		a = sol[K].f.f; b = sol[K].s.f; c = sol[K].f.s; e = sol[K].s.s;
		if (a==1) printf("(x");
		else
		   if (a==-1) printf("(-x");
		   else
	               printf("(%lldx", a);
                if (c>=0) printf("+%lld)", c);
                else
                    printf("-%lld)", -c);

		if (b==1) printf("(x");
		else
		   if (b==-1) printf("(-x");
		   else
	               printf("(%lldx", b);
                   if (e>=0) printf("+%lld)", e);
                   else printf("-%lld)", -e);
		return 0;
}