Cod sursa(job #111815)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 1 decembrie 2007 22:47:25
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 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 = (int)sqrt(delta);
	if ((delta<0)||(a*a<delta)) {printf("-1\n"); return 0; }
	double x1 = (-B-(int)sqrt(delta))/(2*A);
	double x2 = (-B+(int)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));
                       if ((i*i)!=A) 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*d[i].f; y = -x2*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)(x))));
                    x = -x2*d[i].f; y = -x1*d[i].s;
                    if ((x1!=x2)&&(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 (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;
}