#include <iostream>

// With the quadratic formula, you know that the roots
// of the polynomial
//
//        2
//      ax  + bx + c
//
// are
//
//                    __________
//             b     /  2
//          - --- +/- sqrt(b - 4ac)
//            2a
//
// or, more conventionally,
//
//                 __________
//          -b +/- sqrt(b^2 - 4ac)
//      x = ----------------------.
//                    2a
//
// Consequently, if the roots are real, the polynomial
// can be written in the form
//
//     a(x - r1)(x - r2).
//
// In secondary school, however, you also learned
// algorithms for factoring polynomials with integer
// coefficients. For example,
//
//       2
//    18x  + 3x - 105 = 3(2x + 5)(3x - 7).
//
// From this, you can determine that
//
//     the roots are -5/2 and 7/3;
//
//     the x-coordinate of the extremum is -1/12,
//     the average of the two roots; and
//
//     the extremum is a maximum if a < 0 and
//     a minimum if a > 0.
//
// You did not apply the quadratic formula. Instead, you
// applied a sequence of algorithmic steps to factor the
// polynomial into the form
//
//     A(Bx + C)(Dx + E),
//
// where all five values are integers.
//
// Not all quadratic polynomials with integer
// coefficients can be factored in this form, but here
// are some examples:
//
//      2
//   35x  -  55x -  30     5(x - 2)(7x + 3)
//
//      2
//   27x  + 144x + 144     9(3x + 4)(x + 4)
//
//       2
//  504x  - 208x - 192     8(7x - 6)(9x + 4)
//
//      2
//   96x  + 540x + 486     6(2x + 9)(8x + 9)
//
//       2
//  -18x  +  26x +  20    -2(x - 2)(9x + 5)
//
//      2
//   24x  -  16x -  40     8(3x - 5)(x + 1)
//
//      2
//   16x  -  48x +  20     4(2x - 1)(2x - 5)
//
//       2
//  -72x  -  81x + 126    -9(x + 2)(8x - 7)
//
//       2
//  315x  - 115x - 280     5(9x + 7)(7x - 8)
//
//      2
//   24x  -  16x            8x(3x - 2)
//
//       2
//  -64x  - 552x - 320    -8(8x + 5)(x + 8)
//
//      2
//   12x  +   4x -  16     4(x - 1)(3x + 4)
//
//      2
//   20x  +  78x +  28     2(5x + 2)(2x + 7)
//
//      2
//   32x  +  24x            8x(4x + 3)
//
//      2
//   10x  +  15x +   5     5(2x + 1)(x + 1)
//
//      2
//   27x  + 261x + 162     9(3x + 2)(x + 9)


  ////////////////////////////////
 // THE GOALS OF THIS EXERCISE //
////////////////////////////////

// In this exercise, we will implement the steps you
// performed in secondary school to:
//
//   1. factor a quadratic polynomial, if possible;
//   2. print the polynomial;
//   3. print its roots;
//   4. print the x-coordinate of its extremum; and
//   5. determine whether the extremum is a maximum
//      or a minimum.
//
// You performed all these steps on secondary-school
// mathematics assignments and tests. Now we will get
// the computer to do the work.
//
// We could put everything into one enormous main()
// function, but this exercise demonstrates the benefit
// of writing functions to solve self-contained
// subproblems.
//
// A subproblem is a good candidate for a function if,
// given specified parameters, its result depends only
// on those parameters.
//
// Because such a function is self-contained, it can be
// tested independently. Once we have verified that it
// works correctly, we can use it without repeatedly
// investigating its implementation whenever we search
// for a bug elsewhere in the program.

int main() {
    int a{  35 };
    int b{ -55 };
    int c{ -30 };

    // a =  27; b =  144; c =  144;
    // a = 504; b = -208; c = -192;
    // a =  96; b =  540; c =  486;
    // a = -18; b =   26; c =   20;
    // a =  24; b =  -16; c =  -40;
    // a =  16; b =  -48; c =   20;
    // a = -72; b =  -81; c =  126;
    // a = 315; b = -115; c = -280;
    // a =  24; b =  -16; c =    0;
    // a = -64; b = -552; c = -320;
    // a =  12; b =    4; c =  -16;
    // a =  20; b =   78; c =   28;
    // a =  32; b =   24; c =    0;
    // a =  10; b =   15; c =    5;
    // a =  27; b =  261; c =  162;

    return 0;
}

// What steps did you perform when factoring such
// polynomials?








































// You may remember that the first steps are:
//
//   1. If the leading coefficient is negative, factor
//      out -1 so that the remaining leading coefficient
//      is positive.
//
//   2. Find the greatest common divisor of the three
//      coefficients and factor it out. If necessary,
//      include the -1 from Step 1.
//
// For example, given
//
//     a = -72, b = -81, c = 126,
//
// the leading coefficient is negative, so negate all
// three coefficients:
//
//     a = 72, b = 81, c = -126.
//
// The greatest common divisor of these coefficients is
// 9, so divide all three by 9:
//
//     a = 8, b = 9, c = -14.
//
// Thus, so far we have
//
//          2
//     -9(8x + 9x - 14).
//
// The final factored polynomial will have the form
//
//     A(Bx + C)(Dx + E),
//
// where A is the signed greatest common divisor.
//
// Determining the sign does not really require a
// function, but calculating a greatest common divisor
// certainly does.
//
// Recall that
//
//     gcd(a, b, c) = gcd(gcd(a, b), c).
//
// Write a function that calculates the greatest common
// divisor of two integers. Then use it to calculate the
// greatest common divisor of three integers.


















































// Here is my implementation:

/*
int gcd( int a, int b, int c ) {
    // gcd(a, b, c) = gcd(gcd(a, b), c)
    int gcd_ab{ gcd( a, b ) };
    return gcd( gcd_ab, c );

    // This can also be written as
    //
    //     return gcd( gcd( a, b ), c );
    //
    // Which version do you find easier to read?
}

int gcd( int a, int b ) {
    if ( a < 0 ) {
        a = -a;
    }

    if ( b < 0 ) {
        b = -b;
    }

    // We use the conventional definitions
    //
    //     gcd(0, 0) = 0,
    //     gcd(0, b) = |b|,
    //     gcd(a, 0) = |a|.
    //
    // The Euclidean algorithm below already handles
    // all three cases.

    while ( b != 0 ) {
        int tmp{ b };
        b = a%b;
        a = tmp;
    }

    return a;
}
*/
















































// We are now at the stage where
//
//          2
//     -9(8x + 9x - 14)
//
// must be converted to
//
//     -9(Bx + C)(Dx + E).
//
// Expanding the two linear factors gives
//
//     (Bx + C)(Dx + E)
//
//           2
//       = BDx + (BE + CD)x + CE.
//
// Therefore, we require
//
//     BD      = 8,
//     BE + CD = 9,
//     CE      = -14.
//
// Because B and D are positive, we can test the
// positive factor pairs of 8:
//
//     B = 1, D = 8
//     B = 2, D = 4
//     B = 4, D = 2
//     B = 8, D = 1
//
// We need test only the cases where B <= D because
// exchanging the two factors does not change their
// product.
//
// If 'a' is a perfect square, B == D is possible. For
// example,
//
//       2
//     9x - 15x - 14 = (3x + 2)(3x - 7).
//
// Write a loop that finds all pairs B and D satisfying
//
//     BD = a
//
// with
//
//     B <= D.












































// Here is one solution:
//
// for ( int B{ 1 }; B <= a; ++B ) {
//     if ( a%B == 0 ) {
//         int D{ a/B };
//
//         if ( B > D ) {
//             break;
//         }
//
//         std::cout << "One pair is "
//                   << B << " x " << D
//                   << " = " << a
//                   << std::endl;
//     }
// }
//
// This works, but the details of searching for divisors
// make the loop more difficult to read.
//
// Suppose instead we had a function
//
//     next_unsigned_divisor( n, divisor )
//
// that returns the next larger positive divisor of 'n',
// or returns 0 if there is no larger divisor.
//
// Then we could write
//
// int B{ 1 };
//
// while ( B != 0 ) {
//     int D{ a/B };
//
//     if ( B > D ) {
//         break;
//     }
//
//     std::cout << "One pair is "
//               << B << " x " << D
//               << " = " << a
//               << std::endl;
//
//     B = next_unsigned_divisor( a, B );
// }
//
// Humor me: write this function.






















// Here is my implementation:

/*
int next_unsigned_divisor(
    int n,
    int divisor
) {
    // We are guaranteed n > 0.

    // Start searching at divisor + 1 and continue until
    // we find the next divisor of n. If there is no
    // larger divisor, return 0.
    for ( int k{ divisor + 1 }; k <= n; ++k ) {
        if ( n%k == 0 ) {
            return k;
        }
    }

    return 0;
}
*/















// For every pair B and D satisfying BD = a, we must
// test signed factor pairs C and E satisfying
//
//     CE = c.
//
// For example, if c = -14, the possibilities include
//
//     C =   1, E = -14
//     C =  -1, E =  14
//     C =   2, E =  -7
//     C =  -2, E =   7
//     C =   7, E =  -2
//     C =  -7, E =   2
//     C =  14, E =  -1
//     C = -14, E =   1.
//
// We cannot stop after considering only the smaller
// absolute values because C and E play different roles
// in the middle coefficient.
//
// For each pair satisfying BD = a, test the pairs
// satisfying CE = c until
//
//     BE + CD = b.
//
// This suggests a loop within a loop.
//
// Write
//
//     int next_signed_divisor( int n, int divisor );
//
// that allows us to iterate through both positive and
// negative divisors.























// Hint:
//
// One possible order is
//
//     1, -1, 2, -2, 4, -4, 8, -8
//
// for n = 8.
//
// Implement this order.


























// Here is my solution:

/*
int next_signed_divisor(
    int n,
    int divisor
) {
    if ( n < 0 ) {
        n = -n;
    }

    if ( divisor > 0 ) {
        return -divisor;
    }

    // At this point divisor < 0. Search for the next
    // larger positive divisor after -divisor.
    for ( int k{ -divisor + 1 }; k <= n; ++k ) {
        if ( n%k == 0 ) {
            return k;
        }
    }

    return 0;
}
*/















// There is one important special case:
//
//     c == 0.
//
// In this case, every integer technically divides 0,
// so there is no finite list of all divisors to search.
//
// Fortunately, no search is necessary:
//
//       2
//     ax + bx = x(ax + b).
//
// Thus, after the greatest common divisor has been
// factored out, we can immediately choose
//
//     B = 1, C = 0, D = a, E = b.
//
// This also handles examples such as
//
//       2
//     3x - 2x = x(3x - 2).

















// For c != 0, we can now write the two nested loops:
//
// int B{ 1 };
//
// while ( B != 0 ) {
//     int D{ a/B };
//
//     if ( B > D ) {
//         break;
//     }
//
//     int C{ 1 };
//
//     while ( C != 0 ) {
//         int E{ c/C };
//
//         if ( B*E + C*D == b ) {
//             // We have found the factorization.
//         }
//
//         C = next_signed_divisor( c, C );
//     }
//
//     B = next_unsigned_divisor( a, B );
// }
//
// These loops read quite naturally:
//
//     For each factor pair (B, D) satisfying BD = a,
//         test each signed factor pair (C, E)
//         satisfying CE = c.
//
// If
//
//     BE + CD = b,
//
// then
//
//       2
//     ax + bx + c = (Bx + C)(Dx + E).

































// We next want to print either
//
//       A(Bx + C)(Dx + E)
//
// or, if the polynomial cannot be factored over the
// integers,
//
//         2
//       A(ax + bx + c).
//
// We want these expressions printed naturally:
//
//     -(x^2 - 4x - 6)
//
// rather than
//
//     -1(1x^2 + -4x + -6),
//
// and
//
//     (4x - 4)(x + 7)
//
// rather than
//
//     1(4x + -4)(1x + 7).
//
// Write two functions:
//
//     void print_factored_quad_poly(
//         int multiplier,
//         int a1, int b1,
//         int a2, int b2
//     );
//
//     void print_unfactored_quad_poly(
//         int multiplier,
//         int a, int b, int c
//     );
//
// Hint: the factored form prints a linear polynomial
// twice. This suggests another helper function.
//
// Also notice that both forms must print the multiplier.
// That suggests another helper function.

































// To find the roots of
//
//     A(Bx + C)(Dx + E),
//
// solve
//
//     Bx + C = 0
//
// and
//
//     Dx + E = 0.
//
// Thus,
//
//     x = -C/B
//
// and
//
//     x = -E/D.
//
// The x-coordinate of the extremum is the average of
// the two roots:
//
//           1 /  C   E \
//     x = - - | --- + --- |.
//           2 \  B   D /
//
// Because B and D are positive, the sign of the
// leading coefficient is the sign of A. Therefore,
// the extremum is
//
//     a minimum if A > 0,
//     a maximum if A < 0.


































// Finally, we can verify a proposed factorization.
//
// Expanding
//
//     A(Bx + C)(Dx + E)
//
// gives
//
//            2
//     ABD x + A(BE + CD)x + ACE.
//
// Therefore, a factorization of
//
//       2
//     ax + bx + c
//
// is correct exactly when
//
//     ABD            = a,
//     A(BE + CD)     = b,
//     ACE            = c.
//
// A useful verification function would therefore be:
//
// bool verify(
//     int a, int b, int c,
//     int A, int B, int C, int D, int E
// ) {
//     return (A*B*D == a)
//         && (A*(B*E + C*D) == b)
//         && (A*C*E == c);
// }


































// Here is the complete implementation:

// Function declarations
int gcd( int a, int b );
int gcd( int a, int b, int c );

int next_signed_divisor(
    int n,
    int divisor
);

int next_unsigned_divisor(
    int n,
    int divisor
);

void print_coefficient( int coefficient );
void print_lin_poly( int a, int b );

void print_factored_quad_poly(
    int multiplier,
    int a1, int b1,
    int a2, int b2
);

void print_unfactored_quad_poly(
    int multiplier,
    int a, int b, int c
);

void print_roots(
    int B, int C,
    int D, int E
);

void print_extreme(
    int A,
    int B, int C,
    int D, int E
);

// Function definitions
int main() {
    int a{  35 };
    int b{ -55 };
    int c{ -30 };

    // a =  27; b =  144; c =  144;
    // a = 504; b = -208; c = -192;
    // a =  96; b =  540; c =  486;
    // a = -18; b =   26; c =   20;
    // a =  24; b =  -16; c =  -40;
    // a =  16; b =  -48; c =   20;
    // a = -72; b =  -81; c =  126;
    // a = 315; b = -115; c = -280;
    // a =  24; b =  -16; c =    0;
    // a = -64; b = -552; c = -320;
    // a =  12; b =    4; c =  -16;
    // a =  20; b =   78; c =   28;
    // a =  32; b =   24; c =    0;
    // a =  10; b =   15; c =    5;
    // a =  27; b =  261; c =  162;

    // This exercise assumes that the polynomial really
    // is quadratic.
    if ( a == 0 ) {
        return 0;
    }

    // Save the original coefficients so that they could
    // later be used to verify the result.
    int original_a{ a };
    int original_b{ b };
    int original_c{ c };

    // Factor out the sign of the leading coefficient.
    bool negative{ false };

    if ( a < 0 ) {
        negative = true;
        a = -a;
        b = -b;
        c = -c;
    }

    // Factor out the greatest common divisor.
    int A{ gcd( a, b, c ) };

    a /= A;
    b /= A;
    c /= A;

    if ( negative ) {
        A = -A;
    }

    // First deal with the special case c == 0:
    //
    //       2
    //     ax + bx = x(ax + b).
    if ( c == 0 ) {
        int B{ 1 };
        int C{ 0 };
        int D{ a };
        int E{ b };

        print_factored_quad_poly(
            A, B, C, D, E
        );

        print_roots( B, C, D, E );
        print_extreme( A, B, C, D, E );

        return 0;
    }

    // Try all positive factor pairs B*D == a with
    // B <= D.
    int B{ 1 };

    while ( B != 0 ) {
        int D{ a/B };

        if ( B > D ) {
            break;
        }

        // Try all signed factor pairs C*E == c.
        int C{ 1 };

        while ( C != 0 ) {
            int E{ c/C };

            if ( B*E + C*D == b ) {
                print_factored_quad_poly(
                    A, B, C, D, E
                );

                print_roots( B, C, D, E );
                print_extreme( A, B, C, D, E );

                return 0;
            }

            C = next_signed_divisor( c, C );
        }

        B = next_unsigned_divisor( a, B );
    }

    // No integer factorization was found.
    print_unfactored_quad_poly(
        A, a, b, c
    );
    std::cout << std::endl;

    return 0;
}


   /////////////////////////////////
  // Finding the greatest common //
 //  divisor of three integers  //
/////////////////////////////////

// The greatest common divisor of three integers is the
// greatest common divisor of the gcd of the first two
// integers and the third integer.

int gcd( int a, int b, int c ) {
    return gcd( gcd( a, b ), c );
}

// Calculate the greatest common divisor of 'a' and 'b'
// using the Euclidean algorithm.

int gcd( int a, int b ) {
    if ( a < 0 ) {
        a = -a;
    }

    if ( b < 0 ) {
        b = -b;
    }

    while ( b != 0 ) {
        int tmp{ b };
        b = a%b;
        a = tmp;
    }

    return a;
}


  ////////////////////////////////
 // Iterating through divisors //
////////////////////////////////

// Given a non-zero integer 'n' and a signed divisor
// 'divisor' of 'n', return the next signed divisor in
// the sequence
//
//     1, -1, d2, -d2, d3, -d3, ...
//
// If there is no next divisor, return 0.

int next_signed_divisor(
    int n,
    int divisor
) {
    if ( n < 0 ) {
        n = -n;
    }

    if ( divisor > 0 ) {
        return -divisor;
    }

    // At this point, divisor < 0.
    for ( int k{ -divisor + 1 }; k <= n; ++k ) {
        if ( n%k == 0 ) {
            return k;
        }
    }

    return 0;
}

// Given a positive integer 'n' and a positive divisor
// 'divisor' of 'n', return the next larger positive
// divisor. If there is no larger divisor, return 0.

int next_unsigned_divisor(
    int n,
    int divisor
) {
    for ( int k{ divisor + 1 }; k <= n; ++k ) {
        if ( n%k == 0 ) {
            return k;
        }
    }

    return 0;
}


  ///////////////////////////
 // Printing a polynomial //
///////////////////////////

// Print a coefficient.
//
// If coefficient == 1, print nothing.
//
// If coefficient == -1, print only a minus sign.
//
// Otherwise, print the coefficient.

void print_coefficient( int coefficient ) {
    if ( coefficient == -1 ) {
        std::cout << "-";
    } else if ( coefficient != 1 ) {
        std::cout << coefficient;
    }
}

// Print the linear polynomial
//
//     ax + b.
//
// We assume a > 0.
//
// If b == 0, we also assume a == 1, so print only 'x'.

void print_lin_poly( int a, int b ) {
    if ( b == 0 ) {
        std::cout << "x";
        return;
    }

    if ( a == 1 ) {
        std::cout << "(x";
    } else {
        std::cout << "(" << a << "x";
    }

    if ( b > 0 ) {
        std::cout << " + " << b << ")";
    } else {
        std::cout << " - " << (-b) << ")";
    }
}

// Print
//
//     multiplier(a1*x + b1)(a2*x + b2)
//
// using conventional mathematical formatting.

void print_factored_quad_poly(
    int multiplier,
    int a1, int b1,
    int a2, int b2
) {
    print_coefficient( multiplier );

    if ( (b1 == 0) && (b2 == 0) ) {
        std::cout << "x^2";
    } else {
        print_lin_poly( a1, b1 );
        print_lin_poly( a2, b2 );
    }

    std::cout << std::endl;
}

// Print
//
//                    2
//     multiplier(ax + bx + c)
//
// using conventional mathematical formatting.

void print_unfactored_quad_poly(
    int multiplier,
    int a, int b, int c
) {
    print_coefficient( multiplier );

    if ( multiplier != 1 ) {
        std::cout << "(";
    }

    if ( a == 1 ) {
        std::cout << "x^2";
    } else {
        std::cout << a << "x^2";
    }

    if ( b < 0 ) {
        std::cout << " - " << (-b);
    } else if ( b > 0 ) {
        std::cout << " + " << b;
    }

    if ( c < 0 ) {
        std::cout << " - " << (-c);
    } else if ( c > 0 ) {
        std::cout << " + " << c;
    }

    if ( multiplier != 1 ) {
        std::cout << ")";
    }
}


  ///////////////////////////////////////
 // Printing roots and extreme point  //
///////////////////////////////////////

// Print the roots of
//
//     (Bx + C)(Dx + E).
//
// The roots are
//
//     -C/B
//
// and
//
//     -E/D.
//
// Reduce each fraction before printing it.

void print_roots(
    int B, int C,
    int D, int E
) {
    int numer1{ -C };
    int denom1{ B };

    int gcd1{ gcd( numer1, denom1 ) };
    numer1 /= gcd1;
    denom1 /= gcd1;

    int numer2{ -E };
    int denom2{ D };

    int gcd2{ gcd( numer2, denom2 ) };
    numer2 /= gcd2;
    denom2 /= gcd2;

    std::cout << "Roots:" << std::endl;
    std::cout << "   x = "
              << numer1 << "/" << denom1
              << std::endl;
    std::cout << "   x = "
              << numer2 << "/" << denom2
              << std::endl;
}

// Print the x-coordinate of the extremum of
//
//     A(Bx + C)(Dx + E).
//
// The x-coordinate is the average of the two roots:
//
//          /   C     E \ /
//       - |  --- + --- | / 2
//          \   B     D /
//
//              -(CD + EB)
//         = ----------------.
//                 2BD
//
// Because B and D are positive, the sign of the leading
// coefficient is the sign of A.

void print_extreme(
    int A,
    int B, int C,
    int D, int E
) {
    int numer{ -(C*D + E*B) };
    int denom{ 2*B*D };

    int divisor{ gcd( numer, denom ) };

    numer /= divisor;
    denom /= divisor;

    std::cout << "Extreme point:" << std::endl;
    std::cout << "   x = "
              << numer << "/" << denom
              << std::endl;

    if ( A > 0 ) {
        std::cout << "This is a minimum."
                  << std::endl;
    } else {
        std::cout << "This is a maximum."
                  << std::endl;
    }
}