Cod sursa(job #323702)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 13 iunie 2009 10:13:01
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.55 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<utility>
#define tip long long
#define per pair<tip,tip>
using namespace std;
per pd;
pair < per, per > des;
vector< per > dv;
vector< pair< per,per > > desc;
tip a,b,c,k,p1,p2,q1,q2,w,d,RD,D,Rd(),lcm(tip aa,tip bb),i,ndv,ndesc,f1,f2,P1,P2,Q1,Q2,semn;
double rd;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("ecuatie.in","r",stdin);
	freopen("ecuatie.out","w",stdout);
	scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
}
void solve()
{
	d=Rd();
	if(!(d+1)){printf("-1\n");return;}
	q1=-b-d;p1=2*a;w=lcm(p1,q1);p1/=w;q1/=w;q1=-q1;
	q2=-b+d;p2=2*a;w=lcm(p2,q2);p2/=w;q2/=w;q2=-q2;
	a/=p1;a/=p2;
	if(a>0)semn=1;
	else{semn=-1;a=-a;}
	for(i=1;;i++)
	{
		if(i*i>a)break;
		if(a%i)continue;
		if(i<a/i)
		{
			f1=semn*i;f2=a/i;
			des.first.first=f1*p1;
		    des.first.second=f1*q1;
		    des.second.first=f2*p2;
		    des.second.second=f2*q2;
		    desc.push_back(des);ndesc++;
			des.first.first=f2*p1;
		    des.first.second=f2*q1;
		    des.second.first=f1*p2;
		    des.second.second=f1*q2;
		    desc.push_back(des);ndesc++;
		    des.first.first=-f1*p1;
		    des.first.second=-f1*q1;
		    des.second.first=-f2*p2;
		    des.second.second=-f2*q2;
		    desc.push_back(des);ndesc++;
			des.first.first=-f2*p1;
		    des.first.second=-f2*q1;
		    des.second.first=-f1*p2;
		    des.second.second=-f1*q2;
		    desc.push_back(des);ndesc++;
		    if(D)
			{
				des.first.first=-f2*p2;
				des.first.second=-f2*q2;
				des.second.first=-f1*p1;
				des.second.second=-f1*q1;
				desc.push_back(des);ndesc++;
				des.first.first=f1*p2;
				des.first.second=f1*q2;
				des.second.first=f2*p1;
				des.second.second=f2*q1;
				desc.push_back(des);ndesc++;
				des.first.first=f2*p2;
				des.first.second=f2*q2;
				des.second.first=f1*p1;
				des.second.second=f1*q1;
				desc.push_back(des);ndesc++;
				des.first.first=-f1*p2;
				des.first.second=-f1*q2;
				des.second.first=-f2*p1;
				des.second.second=-f2*q1;
				desc.push_back(des);ndesc++;
		    }
			continue;
		}
		f1=semn*i;f2=i;
		des.first.first=f1*p1;
		des.first.second=f1*q1;
		des.second.first=f2*p2;
		des.second.second=f2*q2;
		desc.push_back(des);ndesc++;
		des.first.first=-f1*p1;
		des.first.second=-f1*q1;
		des.second.first=-f2*p2;
		des.second.second=-f2*q2;
		desc.push_back(des);ndesc++;
		if(D)
		{
			des.first.first=f1*p2;
			des.first.second=f1*q2;
			des.second.first=f2*p1;
			des.second.second=f2*q1;
			desc.push_back(des);ndesc++;
			des.first.first=-f1*p2;
			des.first.second=-f1*q2;
			des.second.first=-f2*p1;
			des.second.second=-f2*q1;
			desc.push_back(des);ndesc++;
		}
		break;
	}
	if(k>ndesc){printf("-1\n");return;}
	sort(desc.begin(),desc.end());
	P1=desc[k-1].first.first;
	if(P1-1)
		if(P1+1)
			printf("(%lldx",P1);
		else 
			printf("(-x");
	else printf("(x");
	
	Q1=desc[k-1].first.second;
	if(Q1>0)printf("+");
	printf("%lld)",Q1);
	
	P2=desc[k-1].second.first;
	if(P2-1)
		if(P2+1)
			printf("(%lldx",P2);
		else 
			printf("(-x");
	else printf("(x");
	
	Q2=desc[k-1].second.second;
	if(Q2>0)printf("+");
	printf("%lld)\n",Q2);
}
tip Rd()
{
	D=b*b-4*a*c;
	if(D<0)return -1;
	if(D==0)return 0;
	rd=(double)D;
	rd=sqrt(rd);
	RD=(tip)rd;
	if((RD-1)*(RD-1)==D)return RD-1;
	if(RD*RD==D)return RD;
	if((RD+1)*(RD+1)==D)return RD+1;
	return -1;
}
tip lcm(tip aa,tip bb)
{
	tip rr;
	aa=aa>0?aa:-aa;
	bb=bb>0?bb:-bb;
	while(bb){rr=aa%bb;aa=bb;bb=rr;}
	return aa;
}