Cod sursa(job #343479)

Utilizator ProtomanAndrei Purice Protoman Data 25 august 2009 23:14:52
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <math.h>

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

using namespace std;

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

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

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

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

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

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

	int cmmdc = abs(gcd(abs(a), gcd(abs(b), abs(c))));

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

	for (int i = 0; i < vctDiviz.size(); i++)
	{
		int p1 = (-b - sqrt((double) b * b - 4 * a * c));
		int p2 = (-b + sqrt((double) b * b - 4 * a * c));
		vctSol.pb(mp(mp(vctDiviz[i].f * (2 * a) / gcd(p1, 2 * a), vctDiviz[i].f * p1 / gcd(p1, 2 * a)), mp(vctDiviz[i].s * (2 * a) / gcd(p2, 2 * a), vctDiviz[i].s * p2 / gcd(p2, 2 * a))));
		vctSol.pb(mp(mp(vctDiviz[i].f * (2 * a) / gcd(p2, 2 * a), vctDiviz[i].f * p2 / gcd(p2, 2 * a)), mp(vctDiviz[i].s * (2 * a) / gcd(p1, 2 * a), vctDiviz[i].s * p1 / gcd(p1, 2 * a))));
	}

	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);
	}

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