Cod sursa(job #110147)

Utilizator tvladTataranu Vlad tvlad Data 25 noiembrie 2007 18:45:06
Problema Ecuatie Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 10;

struct fact { int f,e; };
struct solutie { int p1,q1,p2,q2; };

int p1,q1,p2,q2,a,b,c,k;
vector<int> pr;
vector<fact> ad;
vector<fact> cd;
vector<fact> xp;
vector<fact> xq;
vector<solutie> s;

// a = p1*p2
// b = p1*q2 + p2*q1
// c = q1*q2

void descomp ( int x, vector<fact> &nd ) {
	int n, ni;
	if (x < 0) n = x*(-1); else n = x;
	ni = n;
	for (int i = 2; i*i <= ni; ++i) {
		if (n % i == 0) {
			fact f; f.f = i;
			for (f.e = 0; n % i == 0; ++f.e, n /= i);
			nd.push_back(f);
		}
	}
}

int comp ( vector<fact> d ) {
	int r = 1;
	for (int i = 0; i<d.size(); ++i) {
		int x = 1;
		for (int k = 0; k < d[i].e; ++k) x *= d[i].f;
		r *= x;
	}
	return r;
}

void back2 ( int k ) {
// back pentru c -> q1
	for (xq[k].e = 0; xq[k].e <= cd[k].e; ++xq[k].e) {
		if (k < cd.size()-1) {
			back2(k+1);
		} else {
			q1 = comp(xq);
			q2 = c/q1;
			if (p1*q2 + p2*q1 == b) {
				solutie ss = {p1,q1,p2,q2};
				s.push_back(ss);
			}
			q1 = -q1;
			q2 = c/q1;
			if (p1*q2 + p2*q1 == b) {
				solutie ss = {p1,q1,p2,q2};
				s.push_back(ss);
			}
		}
	}	
}

void back1 ( int k ) {
// back pentru a -> p1
	for (xp[k].e = 0; xp[k].e <= ad[k].e; ++xp[k].e) {
		if (k < ad.size()-1) {
			back1(k+1);
		} else {
			p1 = comp(xp);
			p2 = a/p1;
			back2(0);
			p1 = -p1;
			p2 = a/p1;
			back2(0);
		}
	}
}

bool scmp ( const solutie& a, const solutie& b ) { return (a.p1 == b.p1) ? (a.q1 < b.q1) : (a.p1 < b.p1); }

void writepair ( int p, int q ) {
	int qn; char semn;
	if (q < 0) {
		qn = -q;
		semn = '-';
	} else {
		qn = q;
		semn = '+';
	}
	if (p == 0) {
		printf("%d",q);
	} else 
	if (p == 1) {
		printf("(x%c%d)",semn,qn);
	} else
	if (p == -1) {
		printf("(-x%c%d)",semn,qn);
	} else {
		printf("(%dx%c%d)",p,semn,qn);
	}
}

int main() {
	freopen("ecuatie.in","rt",stdin);
	freopen("ecuatie.out","wt",stdout);
	scanf("%d %d %d %d",&a,&b,&c,&k);
	descomp(a,ad);
	descomp(c,cd);
	for (int i = 0; i<ad.size(); ++i) xp.push_back(ad[i]);
	for (int i = 0; i<cd.size(); ++i) xq.push_back(cd[i]);
	back1(0);

	sort(s.begin(),s.end(),scmp);

	writepair(s[k-1].p1,s[k-1].q1);
	writepair(s[k-1].p2,s[k-1].q2);
	printf("\n");
	return 0;
}