Cod sursa(job #476501)

Utilizator SpiderManSimoiu Robert SpiderMan Data 11 august 2010 12:11:38
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
# include <algorithm>
# include <cmath>
using namespace std;

typedef long long ll ;
typedef long double ldb ;
const char FIN[] = "ecuatie.in", FOU[] = "ecuatie.out" ;

struct vector {
    ll P1, Q1, P2, Q2 ;
} Q[5000] ;

ll A, B, C, K, l ;
ldb X1, X2 ;

bool operator < ( const vector& lhs , const vector& rhs ) {
    if ( lhs.P1 == rhs.P1 )
        return lhs.Q1 < rhs.Q1;

    return lhs.P1 < rhs.P1;
}

bool unic ( const vector& lhs , const vector& rhs ) {
    if (lhs.P1 == rhs.P1)
        return lhs.Q1 == rhs.Q1;

    return lhs.P1 == rhs.P1;
}

inline void calcul ( void ) {
    ll delta = B * B - A * C * 4 ;
    if ( sqrt ( delta ) == ( ll ) sqrt ( delta ) ) {
         delta = ( ll ) sqrt ( delta ) ;
         X1 = ( ldb ) ( - B - delta ) / ( A * 2.0 ) ;
         X2 = ( ldb ) ( - B + delta ) / ( A * 2.0 ) ;
    } else {
        printf ( "-1" ) ;
        X1 = X2 = 0 ;
        return ;
    }
}

inline void verf ( ll d ) {
    ldb a , b ;

    a = - X1 * d , b = - X2 * ( A / d ) ;

    if ( a == ( ll ) a && b == ( ll ) b ) {
        Q[l].Q1 = ( ll ) a ;
        Q[l].P1 = d ;
        Q[l].Q2 = ( ll ) b ;
        Q[l++].P2 = A / d ;
    }

    a = - X2 * d, b = - X1 * ( A / d ) ;

    if ( a == ( ll ) a && b == ( ll ) b ) {
        Q[l].Q1 = ( ll ) a ;
        Q[l].P1 = d ;
        Q[l].Q2 = ( ll ) b ;
        Q[l++].P2 = A / d ;
    }
}

inline void divizor ( void ) {

    ll k = abs ( A ) , i , cnt ;

    for ( i = 1, cnt = ( 1 << 16 ) ; cnt ; cnt >>= 1 ) {
        if ( ( i + cnt ) * ( i + cnt ) <= k ) {
            i += cnt ;
        }
    }

    k = i ;

    for ( ll d = 1; d <= k; ++d )
        if ( A % d == 0 ) {
            verf ( d ) ;
            verf ( - d ) ;
            verf ( A / d ) ;
            verf ( - A / d ) ;
        }
}

void afis ( int K ) {
    printf ( "(" ) ;

    if ( Q[K].P1 == -1 ) {
        printf ( "-x" ) ;
    } else if ( Q[K].P1 == 1 ) {
        printf ( "x" ) ;
    } else {
        printf ( "%lldx", Q[K].P1 ) ;
    }

    if ( Q[K].Q1 >= 0 ) {
        printf ( "+%lld)(", Q[K].Q1 ) ;
    } else {
        printf ( "%lld)(", Q[K].Q1 ) ;
    }

     if ( Q[K].P2 == -1 ) {
        printf ( "-x" ) ;
    } else if ( Q[K].P2 == 1 ) {
        printf ( "x" ) ;
    } else {
        printf ( "%lldx", Q[K].P2 ) ;
    }

    if ( Q[K].Q2 >= 0 ) {
        printf ( "+%lld)", Q[K].Q2 ) ;
    } else {
        printf ( "%lld)", Q[K].Q2 ) ;
    }

}

int main ( void ) {
    freopen ( FIN, "r", stdin ) ;
    freopen ( FOU, "w", stdout ) ;

    scanf ( "%lld %lld %lld %lld", &A, &B, &C, &K ) ;

    calcul () ;

    if ( X1 && X2 ) {
        divizor ( ) ;

        sort ( Q , Q + l ) ;

        l = unique ( Q, Q + l, unic ) - Q ;

        if ( K > l ) {
            printf ( "-1" ) ;
        } else {
            afis ( K - 1 ) ;
        }
    }
    return 0;
}