Cod sursa(job #111749)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 1 decembrie 2007 20:00:56
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 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

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

int main()
{
	freopen("ecuatie.in", "r", stdin);
	freopen("ecuatie.out", "w", stdout);
	scanf("%d%d%d%d", &A, &B, &C, &K);
	int 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 (A/i>i) d.pb(mp(A/i,i)), d.pb(mp(-A/i,-i));
                        d.pb(mp(-i,-A/i));
                    }
                d.pb(mp(A,1)); d.pb(mp(1,A));
                d.pb(mp(-A,-1)); d.pb(mp(-1,-A));
		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,(int)(-x1*d[i].f)),mp(d[i].s,(int)(-x2*d[i].s))));

                     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,(int)(-x2*d[i].f)),mp(d[i].s,(int)(-x1*d[i].s))));
                }

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

                nrd = sol.size();

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

                /*for (i = 0; i < nrd; i++)
                    printf("%d %d %d %d\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("(%dx", a);
		if (c==1) printf("+1)");
		else
		   if (c==-1) printf("-1)");
		   else
	               if (c>=0) printf("+%d)", c);
			else
			    printf("-%d)", -c);

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