Cod sursa(job #237208)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 29 decembrie 2008 12:00:55
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

long a, b, c, k, delta, x1, x2, aux, i, v[1024], p, m[1024][9], o, y[1024][9], r;
long a1,a2,b1,b2;

int cmp(const void *a, const void *b) {
	long *c = (long *)a;
	long *d = (long *)b;
	if (c[1] == d[1]) {
		return c[2] - d[2];
	} else {
		return c[1] - d[1];
	}
}

void elimin() {
	++r;
	for (long j = 1; j <= 4; ++j) {
		y[r][j] = m[1][j];
	}
	for (long i = 2; i <= o; ++i) {
		if (m[i][1] != m[i - 1][1] || m[i][2] != m[i - 1][2] || m[i][3] != m[i - 1][3] || m[i][4] != m[i - 1][4]) {
			++r;
			for (long j = 1; j <= 4; ++j) {
				y[r][j] = m[i][j];
			}
		}
	}
	o = r;
	for (long i = 1; i <= o; ++i) {
		for (long j = 1; j <= 4; ++j) {
			m[i][j] = y[i][j];
		}
	}
}
long cmmdc(long a,long b)
{
	if(a<0) a = -a;
	if(b<0) b = -b;
	if( a == 0 || b == 0 )
		return a+b;
	if( a < b)
		b = b%a;
	else a = a%b;
	return cmmdc(a,b);
}

void test(long a,long b)
{
	if( a % b1 || b % b2) return;
	v[++p] = a;
}

int main() {
	freopen("ecuatie.in", "r", stdin);
	freopen("ecuatie.out", "w", stdout);
	scanf("%ld%ld%ld%ld", &a, &b, &c, &k);
	delta = b * b - 4 * a * c;
	if (sqrt(delta) * sqrt(delta) != delta) {
		printf("-1");
		return 0;
	}
	a1 = -b - sqrt(delta), a2 = -b+sqrt(delta);
	b1 = 2*a, b2 = 2*a;
	long c1 = cmmdc(a1,b1), c2 = cmmdc(a2,b2);
	a1/=c1; b1/=c1; a2/=c2; b2/=c2;
	
	aux = sqrt(abs(a));
	for (i = 1; i <= aux; ++i) {
		if (a % i == 0) {
			test(i,a/i);
			test(-i,-(a/i));
			test(a/i,i);
			test(-(a/i),-i);
			
		}
	}
	for (i = 1; i <= p; ++i) {
		m[++o][1] = v[i];
		m[o][3] = a / v[i];
		m[o][2] = - (m[o][1] / b1 * a1);
		m[o][4] = - (m[o][3] / b2 * a2);
		m[++o][1] = v[i];
		m[o][3] = a / v[i];
		m[o][2] = - (m[o][1] / b2 * a2);
		m[o][4] = - (m[o][3] / b1 * a1);
		
	}
	qsort(m + 1, o, sizeof(m[0]), cmp);	
	elimin();
	if (k <= o) {
		printf("(");
		if (m[i][1] == 1) {
			printf("x");
		} else {
			if (m[i][1] == -1) {
				printf("-x");
			} else {
				printf("%ldx", m[i][1]);
			}
		}
		if (m[i][2] >= 0) {
			printf("+%ld)", m[i][2]);
		} else {
			printf("%ld)", m[i][2]);
		}
		printf("(");
		if (m[i][3] == 1) {
			printf("x");
		} else {
			if (m[i][3] == -1) {
				printf("-x");
			} else {
				printf("%ldx", m[i][3]);				
			}
		}
		if (m[i][4] >= 0) {
			printf("+%ld)", m[i][4]);
		} else {
			printf("%ld)", m[i][4]);
		}
		printf("\n");
	}
	if (k > o) {
		printf("-1");
		return 0;
	}
	return 0;
}