Cod sursa(job #361069)

Utilizator ProtomanAndrei Purice Protoman Data 3 noiembrie 2009 17:59:41
Problema Ecuatie Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <math.h>

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

using namespace std;

ll a, b, c, k, x1, x2;
vector <ll> vctDiviz;
vector <pair <pair <ll, ll>, pair <ll, ll> > > vctSol;

inline ll llabs(ll x)
{
	return (x < 0)? -x : x;
}

inline ll gcd(ll a, ll b)
{
	if (!b)
		return a;
	return gcd(b, a % b);
}

inline void form(ll coef, ll af)
{
	printf("(");
	if (coef < 0 && coef == -1)
		printf("-");
	if (coef != 1 && coef != -1)
		printf("%lld", coef);
	printf("x");

	if (af > 0)
		printf("+");
	printf("%lld)", af);
}

int main()
{
	freopen("ecuatie.in", "r", stdin);
	freopen("ecuatie.out", "w", stdout);

	scanf("%lld %lld %lld %lld", &a, &b, &c, &k);
	k--;

	ll cmmdc = llabs(gcd(llabs(a), gcd(llabs(b), llabs(c))));
	a /= cmmdc;
	b /= cmmdc;
	c /= cmmdc;

	for (ll diviz = 1; diviz * diviz <= cmmdc; diviz++)
		if (cmmdc % diviz == 0)
		{
			vctDiviz.pb(diviz);
			vctDiviz.pb(-diviz);
			
			if (diviz * diviz != cmmdc)
			{
				vctDiviz.pb(cmmdc / diviz);
				vctDiviz.pb(-cmmdc / diviz);
			}
		}

	if ((ll) sqrt((long double) b * b - 4 * a * c) * sqrt((long double) b * b - 4 * a * c) != b * b - 4 * a * c)
	{
		printf("-1\n");
		return 0;
	}

	ll q1 = -(-b - (ll) sqrt((long double) b * b - 4 * a * c));
	ll q2 = -(-b + (ll) sqrt((long double) b * b - 4 * a * c));

	ll p1 = 2 * a, p2 = 2 * a;
	if (q1 * p1 > 0)
		q1 = llabs(q1), p1 = llabs(p1);
	if (q2 * p2 > 0)
		q2 = llabs(q2), p2 = llabs(p2);
	if (p1 < 0)
		q1 = -q1, p1 = -p1;
	if (p2 < 0)
		q2 = -q2, p2 = -p2;

	ll x = gcd(llabs(p1), llabs(q1));
	q1 /= x;
	p1 /= x;
	x = gcd(llabs(p2), llabs(q2));
	q2 /= x;
	p2 /= x;
	
	for (int i = 0; i < vctDiviz.size(); i++)
	{
		ll div = vctDiviz[i];
		vctSol.pb(mp(mp(p1 * div, q1 * div), mp(p2 * (cmmdc / div), q2 * (cmmdc / div))));
		vctSol.pb(mp(mp(p2 * div, q2 * div), mp(p1 * (cmmdc / div), q1 * (cmmdc / div))));
	}

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

	if (k >= vctSol.size())
		printf("-1\n");
	else
	{
		form(vctSol[k].f.f, vctSol[k].f.s);
		form(vctSol[k].s.f, vctSol[k].s.s);
		printf("\n");
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}