Cod sursa(job #111820)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 1 decembrie 2007 23:01:41
Problema Ecuatie Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 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, 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 = (long long)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 = 1; i*i <= A; i++)
		    if (A%i==0)
                    {
                        d.pb(mp(i,A/i)); d.pb(mp(-i,-A/i));
                        d.pb(mp(A/i,i)), d.pb(mp(-A/i,-i));
                    }
		sort(d.begin(),d.end());

                nrd = d.size();

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

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

                nrd = sol.size();
                if (nrd>0) Sol.pb(mp(mp(sol[0].f.f,sol[0].f.s),mp(sol[0].s.f,sol[0].s.s)));
                for (i = 1; i < nrd; i++)
                    if ( (sol[i].f.f!=sol[i-1].f.f)||(sol[i].f.s!=sol[i-1].f.s)||(sol[i].s.f!=sol[i-1].s.f)||(sol[i].s.s!=sol[i-1].s.s) )
                         Sol.pb(mp(mp(sol[i].f.f,sol[i].f.s),mp(sol[i].s.f,sol[i].s.s)));

                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==1) printf("+1)");
		else
		   if (c==-1) printf("-1)");
		   else
	               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==1) printf("+1)");
		else
		   if (e==-1) printf("-1)");
		   else
	               if (e>=0) printf("+%lld)", e);
			else
			    printf("-%lld)", -e);
		return 0;
}