Cod sursa(job #428300)

Utilizator nandoLicker Nandor nando Data 29 martie 2010 09:28:15
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 1000000

struct eq{
	long long p1,p2,q1,q2;
	bool operator == (eq s){
		return s.p1==p1&&s.q1==q1;
	}
};

vector <eq> sol;

long long ns=0,ns2=0;
long long a,b,c,k,c1,c2,dd;
long long d,i;

void printeq(eq s){
	printf("(");
	if(s.p1!=1&&s.p1!=-1){
		printf("%lld",s.p1);
	}else if(s.p1==-1){
		printf("-");
	}
	printf("x%c%lld)(",(s.q1>0)?'+':'-',(s.q1>0)?s.q1:-s.q1);
	if(s.p2!=1&&s.p2!=-1){
		printf("%lld",s.p2);
	}else if(s.p2==-1){
		printf("-");
	}
	printf("x%c%lld)\n",(s.q2>0)?'+':'-',(s.q2>0)?s.q2:-s.q2);
}

void addSol(long long s){
	eq tmp;
	if(((s*c1)%dd==0)&&(c2*a)%(dd*s)==0){
		tmp.p1=s;
		tmp.q1=-(c1*s)/dd;
		tmp.p2=a/s;
		tmp.q2=-(c2*a)/(s*dd);
		sol.push_back(tmp);
	}
	if(((s*c2)%dd==0)&&(c1*a)%(dd*s)==0){
		tmp.p1=s;
		tmp.q1=-(c2*s)/dd;
		tmp.p2=a/s;
		tmp.q2=-(c1*a)/(s*dd);
		sol.push_back(tmp);
	}
}
bool cmp(eq  v1,eq v2){
	if(v1.p1==v2.p1){
		return v1.q1<v2.q1;
	}else{
		return v1.p1<v2.p1;
	}
}
int main(){

	FILE* fin=fopen("ecuatie.in","r");
	freopen("ecuatie.out","wt",stdout);
	fscanf(fin,"%lld %lld %lld %lld",&a,&b,&c,&k);
	d=b*b-4*a*c;
	i=(long long)sqrt(abs(d));
	if(d>=0&&i*i==d){
		c1=-b-i,c2=-b+i,dd=2*a;

		long long l=sqrt(abs((long double)a));

		for(long long i=1;i<=l;i++){
			if(a%i==0){
				addSol(i),addSol(-i);
				addSol(a/i),addSol(-a/i);
			}
		}
		sort(sol.begin(),sol.end(),cmp);
		ns=unique(sol.begin(),sol.end())-sol.begin();
		if(k<=ns){
			printeq(sol[k-1]);
		}else{
			printf("-1");
			return 0;
		}
	}else{
		printf("-1");
	}
	return 0;
}