Cod sursa(job #115941)

Utilizator filipbFilip Cristian Buruiana filipb Data 17 decembrie 2007 14:08:45
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <stdio.h>
#include <math.h>

#define ll long long
#define EPS 1e-16

int A, B, C, K, Q, D[60005], nr_q;
double delta;
ll r;

int cmp(double a, double b)
{
    if (fabs(a-b) < EPS) return 1;
    return 0;
}

void swap(int &a, int &b)
{
    int aux = a;
    a = b;
    b = aux;    
}

void show_term(ll P1, ll Q1)
{
    printf("(");
    if (P1 == 1)       printf("x");
    else if (P1 == -1) printf("-x");
    else               printf("%lldx", P1);
    if (Q1 > 0)
        printf("+%lld", Q1);
    else
        printf("%lld", Q1);
    printf(")");
}

void dec(ll P1, ll Q1)
{
     K--;
     if (!K)
     {
         show_term(P1, Q1);
         show_term((ll)A/P1, (ll)C/Q1);
         printf("\n");
     }
}

int main(void)
{
    int i, to, x, sg = +1;
    ll x1, x2, aux;
    
    freopen("ecuatie.in", "r", stdin);
    freopen("ecuatie.out", "w", stdout);

    scanf("%d %d %d %d", &A, &B, &C, &K);
    
    delta = (double)((ll)B * B - (ll)4 * A * C);
    if (delta < 0)
        r = 0;
    else
        r = (ll)sqrt(delta);
    
    if (!cmp((double)r * r, delta))
        printf("-1\n");
    else
    {
        if (A < 0) sg = -1, A = -A;
        to = (int)sqrt(A);
        D[nr_q = 1] = 1;
        for (i = 2; i <= to; i++)
            if (A % i == 0)
                D[++nr_q] = i;
        x = nr_q;
        
        if (to * to == A)
            x--;

        for (i = x; i >= 1; i--)
            D[++nr_q] = A / D[i];

        for (i = 1; i <= nr_q; i++)
            D[i+nr_q] = D[i];
        for (i = 1; i <= nr_q/2; i++)
            swap(D[i], D[nr_q-i+1]);
        for (i = 1; i <= nr_q; i++)
            D[i] = -D[i];
        nr_q <<= 1;

        A *= sg;
        for (i = 1; i <= nr_q && K; i++)
        {
            x1 = x2 = 0;
            if (((ll)2 * D[i] * C) % (r+B) == 0)
            {
                x1 = ((ll)2 * D[i] * C) / (r+B);
                if (C % x1 != 0)
                    x1 = 0;
            }
            if (((ll)2 * D[i] * C) % (-r+B) == 0)
            {
                x2 = ((ll)2 * D[i] * C) / (-r+B);
                if (C % x2 != 0)
                    x2 = 0;
            }

            if (x1 > x2)
                aux = x1, x1 = x2, x2 = aux;
            if (x1 == x2) x2 = 0;
            
            if (x1 && K)
                dec(D[i], x1);
            if (x2 && K)
                dec(D[i], x2);
        }

        if (K > 0)
            printf("-1\n");
            
/*        for (i = 1; i <= nr_q; i++)
            printf("%d ", D[i]);
        printf("\n");*/
    }

    return 0;
}