Cod sursa(job #965049)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 23 iunie 2013 01:25:33
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include<stdio.h>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cstdlib>

using namespace std;

FILE*f=fopen("ecuatie.in","r");
FILE*g=fopen("ecuatie.out","w");

int a,b,c,k;
long long numarator1,numitor1,numarator2,numitor2;
vector< pair<int,pair<long long,pair<int,long long> > > >sol;

inline void nosol () {
	
	fprintf(g,"-1\n");
	fclose(f); fclose(g);
	exit(0);
}

inline long long get_sqrt ( const long long &N ){
	
	long long left = 0,middle,right = 2236067979LL;
	while ( left <= right ){
		middle = (left+right)>>1;
		if ( middle*middle <= N ){
			left = middle+1;
		}
		else{
			right = middle-1;
		}
	}
	
	return right;
}

inline void baga ( const int &i , const int &j ){
	
	if ( (i*numarator1 % numitor1) || (j*numarator2 % numitor2) ){
		return ;
	}
	
	sol.push_back(make_pair(i,make_pair(-(i*numarator1 / numitor1),make_pair(j,-(j*numarator2 / numitor2)))));
}

inline void get_posibilities () {
	
	int modul_a = a;
	if ( modul_a < 0 )	modul_a = -modul_a;
	
	for ( int i = 1 ; i*i <= modul_a ; ++i ){
		if ( modul_a % i )	continue ;
		
		int other = a/i;
		baga(i,other);
		baga(-i,-other);
		baga(other,i);
		baga(-other,-i);
	}
}

inline void afiseaza ( const pair<int,pair<long long,pair<int,long long> > > &x ){
	long long p1,q1,p2,q2;
	p1 = x.first,q1 = x.second.first,p2 = x.second.second.first,q2 = x.second.second.second;
	
	fprintf(g,"(");
	
	if ( p1 != 1 ){
		if ( p1 == -1 ){
			fprintf(g,"-");
		}
		else{
			fprintf(g,"%lld",p1);
		}
	}
	fprintf(g,"x");
	
	if ( q1 >= 0 ){
		fprintf(g,"+%lld",q1);
	}
	else{
		fprintf(g,"%lld",q1);
	}
	
	fprintf(g,")(");
	
	if ( p2 != 1 ){
		if ( p2 == -1 ){
			fprintf(g,"-");
		}
		else{
			fprintf(g,"%lld",p2);
		}
	}
	fprintf(g,"x");
	
	if ( q2 >= 0 ){
		fprintf(g,"+%lld",q2);
	}
	else{
		fprintf(g,"%lld",q2);
	}
	
	fprintf(g,")");
}

int main () {
	
	fscanf(f,"%d %d %d %d",&a,&b,&c,&k);
	
	long long delta = 1LL*b*b - 4LL*a*c;
	if ( delta < 0 ){
		nosol();
	}
	
	long long rad = get_sqrt(delta);
	if ( rad*rad != delta ){
		nosol();
	}
	
	numarator1 = -b-rad,numitor1 = a+a,numarator2 = -b+rad,numitor2 = a+a;
	
	get_posibilities();
	
	swap(numarator1,numarator2);
	swap(numitor1,numitor2);
	
	get_posibilities();
	
	sort(sol.begin(),sol.end());
	sol.resize(unique(sol.begin(),sol.end())-sol.begin());
	
	if ( sol.size() < k ){
		nosol();
	}
	
	afiseaza(sol[k-1]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}