Cod sursa(job #430173)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 30 martie 2010 20:03:44
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;
long long l,x,x1s,x1j,x2s,x2j,A,B,C,k,auxp1,auxp2,auxq1,auxq2;
struct sol
{
	long long x,y,z,t;
} m[100000];
bool comp(const sol &A,const sol &B)
{
	if(A.x>B.x) return false;
	if(A.x<B.x) return true;
	if(A.y>B.y) return false;
	return true;
}
long long modul(long long x)
{
	return x<0?(-x):x;
}
void getsol(long long d)
{
	long long p1,p2,q1,q2;
	p1=d;
	q1=-x1s*d/x1j;
	p2=A/d;
	q2=-x2s*A/(d*x2j);
	if((p1*p2==A && q1*q2==C && p1*q2+p2*q1==B) || (p1*p2==-A && q1*q2==-C && p1*q2+p2*q1==-B))
	{
		bool ok=true;
		for(int i=1;i<=l;i++)
			if(m[i].x==p1 && m[i].y==q1 && m[i].z==p2 && m[i].t==q2)
			{
				ok=false;
				break;
			}
		if(ok==true)
		{
			++l;
			m[l].x=p1;
			m[l].y=q1;
			m[l].z=p2;
			m[l].t=q2;
		}
	}
	p1=d;
	q1=-x2s*d/x2j;
	p2=A/d;
	q2=-x1s*A/(d*x1j);
	if((p1*p2==A && q1*q2==C && p1*q2+p2*q1==B) || (p1*p2==-A && q1*q2==-C && p1*q2+p2*q1==-B))
	{
		bool ok=true;
		for(int i=1;i<=l;i++)
			if(m[i].x==p1 && m[i].y==q1 && m[i].z==p2 && m[i].t==q2)
			{
				ok=false;
				break;
			}
		if(ok==true)
		{
			++l;
			m[l].x=p1;
			m[l].y=q1;
			m[l].z=p2;
			m[l].t=q2;
		}
	}
}
long long getx1x2()
{
	long long delta=B*B-4*A*C;
	if((long long)sqrt(delta)*sqrt(delta)!=sqrt(delta)*sqrt(delta))
		return 0;
	x1s=-B-(long long)sqrt(delta);
	x1j=2*A;
	x2s=-B+(long long)sqrt(delta);
	x2j=2*A;
	return 1;
}
int main()
{
	freopen("ecuatie.in","r",stdin);
	freopen("ecuatie.out","w",stdout);
	scanf("%lld%lld%lld%lld",&A,&B,&C,&k);
	if(!getx1x2())
	{
		printf("-1");
		return 0;
	}
	x=(int)sqrt(modul(A));
	for(int i=1;i<=x;i++)
		if(A%i==0)
			getsol(i), getsol(-i), getsol(A/i), getsol(-A/i);
	sort(m+1,m+l+1,comp);
	if(!m[k].x) printf("-1");
	else
	{
		printf("(");
		if(m[k].x==-1) printf("-");
			else if(m[k].x!=1) printf("%lld",m[k].x);
		printf("x");
		if(m[k].y<0) printf("%lld",m[k].y);
			else printf("+%lld",m[k].y);
		printf(")(");
		if(m[k].z==-1) printf("-");
			else if(m[k].z!=1) printf("%lld",m[k].z);
		printf("x");
		if(m[k].t<0) printf("%lld",m[k].t);
			else printf("+%lld",m[k].t);
		printf(")");
	}
	return 0;
}