#include <cstdint>
#include <iostream>

/***************************************************
 * Sums of powers of divisors
 *
 * Previously, you wrote a function that calculates
 * the sum of the positive divisors of an integer.
 *
 * More generally, the divisor function
 *
 *     sigma_k(n)
 *
 * is the sum of the kth powers of the positive
 * divisors of n.
 *
 * For example, the positive divisors of 12 are
 *
 *     1, 2, 3, 4, 6, 12.
 *
 * Thus,
 *
 *     sigma_1(12)
 *
 *       = 1 + 2 + 3 + 4 + 6 + 12
 *
 *       = 28,
 *
 * while
 *
 *     sigma_2(12)
 *
 *       = 1^2 + 2^2 + 3^2 + 4^2 + 6^2 + 12^2.
 *
 *
 * If p is prime, its only positive divisors are
 * 1 and p, so
 *
 *     sigma_k(p) = 1 + p^k.
 *
 *
 * THE DEFAULT ARGUMENT
 *
 * The most commonly encountered divisor sum is
 *
 *     sigma_1(n),
 *
 * so we will give k the default argument 1.
 *
 * Consequently,
 *
 *     sigma( 12 )
 *
 * and
 *
 *     sigma( 12, 1 )
 *
 * calculate the same value.
 *
 *
 * WHAT ABOUT k == 0?
 *
 * For any positive divisor d,
 *
 *     d^0 = 1.
 *
 * Consequently, sigma_0(n) simply counts the
 * number of positive divisors of n.
 *
 * For example,
 *
 *     sigma_0(12) = 6.
 *
 *
 * We restrict n to positive integers. The usual
 * divisor-sum function is not defined for n == 0,
 * because every positive integer divides 0.
 ***************************************************/

// Function declarations
int main();

std::uint64_t sigma(
    std::uint64_t const n,
    std::uint64_t const k = 1
);

std::uint64_t pow(
    std::uint64_t const n,
    std::uint64_t const m
);

// Function definitions
int main() {
    for ( std::uint64_t n{ 1 }; n <= 20; ++n ) {
        std::cout << "sigma(" << n << ", 0) = "
                  << sigma( n, 0 )
                  << std::endl;
    }

    std::cout << std::endl;

    for ( std::uint64_t n{ 1 }; n <= 20; ++n ) {
        std::cout << "sigma(" << n << ") = "
                  << sigma( n )
                  << std::endl;
    }

    std::cout << std::endl;

    for ( std::uint64_t n{ 1 }; n <= 20; ++n ) {
        std::cout << "sigma(" << n << ", 2) = "
                  << sigma( n, 2 )
                  << std::endl;
    }

    return 0;
}

std::uint64_t sigma(
    std::uint64_t const n,
    std::uint64_t const k
) {
    return 0;
}

/***************************************************
 * pow
 *
 * Calculate n^m using exponentiation by squaring.
 ***************************************************/
std::uint64_t pow(
    std::uint64_t const n,
    std::uint64_t const m
) {
    std::uint64_t product{ 1 };
    std::uint64_t n_to_power_of_2{ n };
    std::uint64_t power_of_2{ 1 };

    while ( power_of_2 <= m ) {
        if ( (m & power_of_2) != 0 ) {
            product *= n_to_power_of_2;
        }

        n_to_power_of_2 *= n_to_power_of_2;
        power_of_2 <<= 1;
    }

    return product;
}

























// Hint:
//
// Iterate through all the integers divisor from
// 1 through n.
//
// If
//
//     n % divisor == 0,
//
// then divisor is a divisor of n, so add
//
//     divisor^k
//
// to the sum.
//
// You already have a function that calculates
// integer powers efficiently.














































// Here is one solution:

/*
std::uint64_t sigma(
    std::uint64_t const n,
    std::uint64_t const k
) {
    std::uint64_t sum{ 0 };

    for ( std::uint64_t divisor{ 1 };
          divisor <= n;
          ++divisor ) {
        if ( n%divisor == 0 ) {
            sum += pow( divisor, k );
        }
    }

    return sum;
}
*/