Self powers (C++ ver) Sample by ClearNB

Solution_48.cpp

#include <vector>
#include <iostream>
#include <cmath>

unsigned long long mulmod(unsigned long long a, unsigned long long b, unsigned long long mdlo) {
    a %= mdlo;
    b %= mdlo;
    if (a <= 0xFFFFFFF && b <= 0xFFFFFFF) {
        return (a * b) % mdlo;
    }
    unsigned int leadingZeros = 0;
    unsigned long long m = mdlo;
    while((m & 0x8000000000000000ULL) == 0) {
        leadingZeros++;
        m <<= 1;
    }
    unsigned long long mask = (1 << leadingZeros) - 1;
    unsigned long long result = 0;
    while(a > 0 && b > 0) {
        result += (b & mask) * a;
        result %= mdlo;
        b >>= leadingZeros;
        a <<= leadingZeros;
        a %= mdlo;
    }
    return result;
}

unsigned long long powmod(unsigned long long base, unsigned long long expo, unsigned long long mdlo) {
    unsigned long long result = 1;
    while (expo > 0) {
        if (expo & 1) {
            result = mulmod(result, base, mdlo);
        }
        base = mulmod(base, base, mdlo);
        expo >>= 1;
    }
    return result;
}

int main() {
    unsigned int N;
    std::cin >> N;
    const unsigned long long TenDigits = 10000000000ULL;
    unsigned long long sum = 0;
    for(unsigned int i = 1; i <= N; i++) {
        sum += powmod(i, i, TenDigits);
    }
    std::cout << (sum % TenDigits) << std::endl;
    return 0;
}