#include <cstddef>
#include <iostream>

/***************************************************
 * Greatest common divisor and least common multiple
 *
 * The greatest common divisor (gcd) of three
 * integers is the greatest integer that divides
 * all three integers. Similarly, the least common
 * multiple (lcm) of three integers is the smallest
 * nonnegative integer that is a multiple of all
 * three.
 *
 * We have
 *
 *     gcd( m1, m2, m3 )
 *
 *       = gcd( gcd( m1, m2 ), m3 ).
 *
 * This generalizes to any number of integers.
 *
 * Similarly, for two integers,
 *
 *                     m
 *     lcm( m, n ) = ----- n,
 *                  gcd(m,n)
 *
 * provided neither m nor n is zero. If either is
 * zero, their lcm is zero.
 *
 * However,
 *
 *                             m1*m2*m3
 *     lcm( m1, m2, m3 ) != ----------------
 *                          gcd(m1,m2,m3)
 *
 * in general. For example, consider the integers
 * 2, 3, and 4.
 *
 * Instead, we use
 *
 *     lcm( m1, m2, m3 )
 *
 *       = lcm( lcm( m1, m2 ), m3 ),
 *
 * and this also generalizes to any number of
 * integers.
 ***************************************************/

// Function declarations
unsigned int gcd(
    unsigned int m,
    unsigned int n
);

unsigned int gcd(
    unsigned int const m0,
    unsigned int const m1,
    unsigned int const m2
);

unsigned int gcd(
    unsigned int const array[],
    std::size_t const capacity
);

unsigned int lcm(
    unsigned int const m,
    unsigned int const n
);

unsigned int lcm(
    unsigned int const m0,
    unsigned int const m1,
    unsigned int const m2
);

unsigned int lcm(
    unsigned int const array[],
    std::size_t const capacity
);

int main();

// Function definitions
int main() {
    unsigned int array1[1]{ 42 };

    unsigned int array2[10]{
        66, 66, 6, 54, 18, 36, 24, 18, 36, 54
    };

    unsigned int array3[100]{
        38164, 38164, 63336, 51968, 34916,
        56840, 42224, 52780, 48720, 28420,
        66584, 60088, 47096, 72268, 77952,
        39788,  8120, 34916, 38164, 66584,
        56840, 58464, 78764, 77952, 59276,
        32480,  6496, 22736,  4060,  8932,
        71456, 40600, 45472, 12180, 16240,
        61712, 77952, 38976, 68208, 17864,
        27608, 28420,  4060, 77952,  6496,
        67396, 71456, 66584, 12180,  9744,
        25984, 78764, 43848, 38976, 71456,
        17864, 32480,  6496, 29232, 29232,
        60088, 20300, 61712, 51156, 30044,
        62524, 58464, 45472,  7308, 77952,
         3248, 25172,  7308, 48720, 64960,
        30856,  9744, 23548, 31668,  2436,
        41412, 32480,  5684, 69832, 17864,
        73080,   812, 36540, 79576, 77140,
        23548, 73892, 53592, 38976, 61712,
         4060, 60900, 49532, 28420, 60900
    };

    std::cout << gcd( 5, 0 )
              << " = 5" << std::endl;
    std::cout << lcm( 5, 0 )
              << " = 0" << std::endl;

    std::cout << gcd( 5, 13 )
              << " = 1" << std::endl;
    std::cout << lcm( 5, 13 )
              << " = 65" << std::endl;

    std::cout << gcd( 70, 150 )
              << " = 10" << std::endl;
    std::cout << lcm( 70, 150 )
              << " = 1050" << std::endl;

    std::cout << gcd( 70, 150, 180 )
              << " = 10" << std::endl;
    std::cout << lcm( 70, 150, 180 )
              << " = 6300" << std::endl;

    std::cout << gcd( 12, 0, 8 )
              << " = 4" << std::endl;
    std::cout << lcm( 12, 0, 8 )
              << " = 0" << std::endl;

    // The gcd and lcm of no integers are taken to
    // be 0 and 1, respectively.
    std::cout << gcd( nullptr, 0 )
              << " = 0" << std::endl;
    std::cout << lcm( nullptr, 0 )
              << " = 1" << std::endl;

    std::cout << gcd( array1, 1 )
              << " = 42" << std::endl;
    std::cout << lcm( array1, 1 )
              << " = 42" << std::endl;

    std::cout << gcd( array2, 10 )
              << " = 6" << std::endl;
    std::cout << lcm( array2, 10 )
              << " = 2376" << std::endl;

    // The lcm of all 100 integers cannot be
    // represented by an unsigned int.
    std::cout << gcd( array3, 100 )
              << " = 812" << std::endl;

    std::cout << lcm( array3, 100 )
              << " != "
              << "698197887300518453819432676614400"
              << std::endl;

    // The first three entries have the same gcd,
    // but a smaller and representable lcm.
    std::cout << gcd( array3, 3 )
              << " = 812" << std::endl;
    std::cout << lcm( array3, 3 )
              << " = 2976792" << std::endl;

    return 0;
}

/***************************************************
 * gcd
 *
 * Return the greatest common divisor of m and n
 * using the Euclidean algorithm.
 ***************************************************/
unsigned int gcd(
    unsigned int m,
    unsigned int n
) {
    while ( n != 0 ) {
        unsigned int const remainder{ m % n };

        m = n;
        n = remainder;
    }

    return m;
}

/***************************************************
 * lcm
 *
 * Return the least common multiple of m and n.
 ***************************************************/
unsigned int lcm(
    unsigned int const m,
    unsigned int const n
) {
    if ( (m == 0) || (n == 0) ) {
        return 0;
    }

    return (m/gcd( m, n ))*n;
}

/***************************************************
 * gcd of three integers
 ***************************************************/
unsigned int gcd(
    unsigned int const m0,
    unsigned int const m1,
    unsigned int const m2
) {
    return 0;
}

/***************************************************
 * lcm of three integers
 ***************************************************/
unsigned int lcm(
    unsigned int const m0,
    unsigned int const m1,
    unsigned int const m2
) {
    return 1;
}

/***************************************************
 * gcd of an array of integers
 ***************************************************/
unsigned int gcd(
    unsigned int const array[],
    std::size_t const capacity
) {
    return 0;
}

/***************************************************
 * lcm of an array of integers
 ***************************************************/
unsigned int lcm(
    unsigned int const array[],
    std::size_t const capacity
) {
    return 1;
}




































// Hints:
//
// Recall that
//
//     gcd( a, b, c ) = gcd( gcd( a, b ), c ).
//
// That is, to find the greatest common divisor of
// three integers, first find the gcd of the first
// two and then calculate the gcd of that result and
// the third.
//
// Similarly,
//
//     lcm( a, b, c ) = lcm( lcm( a, b ), c ).
//
//
// To do this with an array of capacity integers,
// observe that
//
//     gcd( a, b, c, d, e, ... )
//
//       = gcd( gcd( a, b ), c, d, e, ... ).
//
//
// The gcd of one value n is n:
//
//     gcd( n ) = n.
//
// What, then, should be the gcd of no values?
//
// We know that
//
//     gcd( 0, n ) = n.
//
// Consequently, if we begin with
//
//     result = 0
//
// then
//
//     result = gcd( result, array[0] );
//     result = gcd( result, array[1] );
//     result = gcd( result, array[2] );
//
// and so on.
//
// If there are no entries, result remains 0.
//
//
// The same idea works for the lcm, except that we
// begin with
//
//     result = 1.
//
// This is because
//
//     lcm( 1, n ) = n.
//
// Thus, for this exercise, the lcm of no values is
// taken to be 1.






































// One solution:

/*
unsigned int gcd(
    unsigned int const m0,
    unsigned int const m1,
    unsigned int const m2
) {
    return gcd( gcd( m0, m1 ), m2 );
}

unsigned int lcm(
    unsigned int const m0,
    unsigned int const m1,
    unsigned int const m2
) {
    return lcm( lcm( m0, m1 ), m2 );
}

unsigned int gcd(
    unsigned int const array[],
    std::size_t const capacity
) {
    unsigned int result{ 0 };

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        result = gcd( result, array[k] );
    }

    return result;
}

unsigned int lcm(
    unsigned int const array[],
    std::size_t const capacity
) {
    unsigned int result{ 1 };

    for ( std::size_t k{ 0 }; k < capacity; ++k ) {
        result = lcm( result, array[k] );
    }

    return result;
}
*/