Cod sursa(job #427749)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 28 martie 2010 13:21:36
Problema Ecuatie Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<cstdio>
#include<fstream>
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#define tip long long
using namespace std;
vector< pair< pair<tip,tip>,pair<tip,tip> > > desc;
tip a,b,c,k,d,RD(),R,L,M,D,i,cmmdc(tip x,tip y),p1,q1,p2,q2,d1,d2,f1,f2,A;
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("ecuatie.in","r",stdin);
	freopen("ecuatie.out","w",stdout);
	cin>>a>>b>>c>>k;
}
void solve()
{
	d=RD();if(d==-1){printf("-1\n");return;}
	p1=2*a;q1=b-d;d1=cmmdc(p1,q1);p1/=d1;q1/=d1;if(p1<0){p1=-p1;q1=-q1;}
	p2=2*a;q2=b+d;d2=cmmdc(p2,q2);p2/=d2;q2/=d2;if(p2<0){p2=-p2;q2=-q2;}
	a/=p1;a/=p2;A=a<0?-a:a;
	for(i=1;;i++)
	{
		if(i*i>A)break;
		if(A%i==0)
		{
			f1=i;f2=a/i;
			desc.push_back(make_pair(make_pair(f1*p1,f1*q1),make_pair(f2*p2,f2*q2)));
			desc.push_back(make_pair(make_pair(-f1*p1,-f1*q1),make_pair(-f2*p2,-f2*q2)));
			if(f1!=f2&&f1+f2!=0)
			{
				desc.push_back(make_pair(make_pair(f2*p1,f2*q1),make_pair(f1*p2,f1*q2)));
				desc.push_back(make_pair(make_pair(-f2*p1,-f2*q1),make_pair(-f1*p2,-f1*q2)));
			}
			if(d)
			{
				desc.push_back(make_pair(make_pair(f1*p2,f1*q2),make_pair(f2*p1,f2*q1)));
				desc.push_back(make_pair(make_pair(-f1*p2,-f1*q2),make_pair(-f2*p1,-f2*q1)));
				if(f1!=f2&&f1+f2!=0)
				{
					desc.push_back(make_pair(make_pair(f2*p2,f2*q2),make_pair(f1*p1,f1*q1)));
					desc.push_back(make_pair(make_pair(-f2*p2,-f2*q2),make_pair(-f1*p1,-f1*q1)));
				}
			}
		}
	}
	sort(desc.begin(),desc.end());
	if(desc.size()<k)printf("-1\n");
	A=desc[k-1].first.first;if(A==1)cout<<"(x";else if(A==-1)cout<<"(-x";else cout<<"("<<A<<"x";
	A=desc[k-1].first.second;if(A>=0)cout<<"+";cout<<A<<")";
	A=desc[k-1].second.first;if(A==1)cout<<"(x";else if(A==-1)cout<<"(-x";else cout<<"("<<A<<"x";
	A=desc[k-1].second.second;if(A>=0)cout<<"+";cout<<A<<")\n";	
}
tip RD()
{
	D=b*b-4*a*c;
	R=1;for(i=1;i<=32;i++)R*=2;
	L=0;
	while(R>L+1)
	{
		M=(R+L)/2;
		if(M*M>D)R=M;
		else L=M;
	}
	if(L*L==D)return L;
	return -1;
}
tip cmmdc(tip x,tip y)
{
	tip r;while(y){r=x%y;x=y;y=r;}return x;
}