Project Euler 48

http://projecteuler.net/index.php?section=problems&id=48

下10桁だけ計算すればよいから64ビットで済むが、64ビット同士の掛け算はできないので、5桁ずつに分けて計算する。

itertools.h

#include <iostream>
#include "itertools.h"

using namespace itertools;

const long long D = (long long)1e10;

long long mul(long long x, long long y) {
    const int   D2 = (int)1e5;
    const long long x0 = x % D2;
    const long long x1 = x / D2;
    const long long y0 = y % D2;
    const long long y1 = y / D2;
    return (x0 * y0 + (x0 * y1 + x1 * y0) * D2) % D;
}

long long pow(int n, int e) {
    if(e == 0)
        return 1;
    
    const long long m = pow(n, e / 2);
    if(e % 2 == 1)
        return mul(mul(m, m), (long long)n);
    else
        return mul(m, m);
}

int main() {
    const int   N = 1000;
    std::cout << sum(map([] (int n) { return pow(n, n); },
                            range<>(1, N + 1))) % D << std::endl;
}