Cod sursa(job #196914)

Utilizator gcosminGheorghe Cosmin gcosmin Data 30 iunie 2008 10:42:01
Problema Ecuatie Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

#define MP make_pair
#define ff first
#define ss second
#define LL long long

int A, B, C, K;

vector <pair<pair<int, int>, pair<int, int> > > sol;

inline int ABS(int x) { return (x < 0) ? -x : x; }

void get_sol(int p1, int p2)
{
	LL a = -p2, b = B, c = (LL) - C * p1;
	LL delta = b * b - 4 * a * c;

	if (delta < 0) return;

	LL step = (LL) 1 << 30, x = 0;

	for (; step; step >>= 1)
		if ((x + step) * (x + step) <= delta)
			x += step;

	if (x * x != delta) return;

	int q1, q2;

	if ( (-b + x) % (2 * a) == 0) {
		q1 = (-b + x) / (2 * a);
		q2 = C / q1;

		sol.push_back(MP( MP(p1, q1), MP(p2, q2) ) );
	}

	if ( (-b - x) % (2 * a) == 0) {
		q1 = (-b - x) / (2 * a);
		q2 = C / q1;

		sol.push_back(MP( MP(p1, q1), MP(p2, q2) ) );
	}
}

void print_jeg(int p1, int q1)
{
	printf("(");

	if (p1 == 1) printf("x");
	else
	if (p1 == -1) printf("-x");
	else printf("%dx", p1);

	if (q1 < 0) printf("%d", q1);
	else printf("+%d", q1);

	printf(")");
}

void print_sol(int p1, int q1, int p2, int q2)
{
	print_jeg(p1, q1);
	print_jeg(p2, q2);
	printf("\n");
}

int main()
{
	int i, p1, p2;

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

	scanf("%d %d %d %d", &A, &B, &C, &K);

	for (i = 1; i * i <= A; i++) {
		if (A % i) continue;

		p1 = i; p2 = A / i;

		get_sol(p1, p2);
		get_sol(p2, p1);

		get_sol(-p1, -p2);
		get_sol(-p2, -p1);
	}

	sort(sol.begin(), sol.end());
	sol.resize( unique(sol.begin(), sol.end()) - sol.begin() );

	if ((int) sol.size() >= K) print_sol(sol[K - 1].ff.ff, sol[K - 1].ff.ss, sol[K - 1].ss.ff, sol[K - 1].ss.ss);
	else printf("-1\n");

return 0;
}