Cod sursa(job #110587)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 26 noiembrie 2007 23:29:42
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <math.h>
#include <assert.h>
#include <vector>
#include <algorithm>

using namespace std;

#define nmax 302
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define mp make_pair
#define f first
#define s second
#define sz size()
#define pb push_back
#define PII pair<lint,lint>

typedef long long lint;

lint n,A,B,C,x1,x2,k;
vector < pair < PII,PII > > Q;

lint mod(lint a) {return a>0?a:-a;}

void doit(lint a,lint b)
{
	if(mod(a*x1)%mod(2*A)||mod(b*x2)%mod(2*A))
		return;
	Q.pb(mp(mp(a,-a*x1/2/A),mp(b,-b*x2/2/A)));
	Q.pb(mp(mp(b,-b*x2/2/A),mp(a,-a*x1/2/A)));
}

void afis(int p1,int q1)
{
	printf("(");
	if(p1!=1&&p1!=-1)
		printf("%d",p1);
	if(p1==-1)
		printf("-");
	printf("x");
	if(q1>0)
		printf("+");
	printf("%d",q1);
	printf(")");
}

int main()
{
	lint i,j,delta,x;
	assert(freopen("ecuatie.in","r",stdin));
	freopen("ecuatie.out","w",stdout);
	assert(scanf("%lld %lld %lld %lld",&A,&B,&C,&k)==4);
	assert(A<=1000000000);
	assert(A>=-1000000000);
	assert(B<=1000000000);
	assert(B>=-1000000000);
	assert(C<=1000000000);
	assert(C>=-1000000000);
	assert(A!=0);
	assert(C!=0);
	delta=B*B-4*A*C;
	x=(lint)sqrt(delta);
	if(x*x==delta)
	{
		x1=-B-x, x2=-B+x;		
		for(i=1;i*i<=mod(A);++i)
			if(A%i==0)
				doit(i,A/i),doit(A/i,i),doit(-i,-A/i),doit(-A/i,-i);
	}

	if(Q.size())
	{
		sort(Q.begin(),Q.end());
		Q.erase(unique(Q.begin(),Q.end()),Q.end());
	}
	if(k<=Q.sz)
		afis(Q[k-1].f.f,Q[k-1].f.s),afis(Q[k-1].s.f,Q[k-1].s.s);
	else
		printf("-1");
	printf("\n");


	return 0;
}