Project Euler 20

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

これも前にで作った多倍長整数クラスを使えば簡単。掛け算は足し算を繰り返すだけ。ただし、単純に足すだけだと芸がないのでバイナリ法を使った。

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

using namespace std;
using namespace itertools;

longint mul(longint n, int m) {
    if(m == 0)
        return 0;
    
    longint p = mul(n, m / 2);
    longint q = p + p;
    if(m % 2 == 1)
        return q + n;
    else
        return q;
}

int main() {
    const int   N = 100;
    longint n = reduce(mul, range<>(1, N + 1), longint(1));
    cout << sum(map([&n] (int k) { return n.at(k); },
                                range<>(n.length()))) << endl;
}

実際のところ、intを掛けるのは簡単なので、*演算子を定義した。

itertools.h

    longint& operator *(int a) {
        longint c = *this;
        return c *= a;
    }
    longint& operator *=(int a) {
        int a1 = a % 10;
        int a2 = a / 10;
        int r = 0;
        for(int k = 0; k < length(); k++) {
            int n = v[k] * a1 + r;
            r = n / 10 + v[k] * a2;
            v[k] = n % 10;
        }
        while(r > 0) {
            v.push_back(r % 10);
            r /= 10;
        }
        return *this;
    }

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

using namespace std;
using namespace itertools;

int main() {
    const int   N = 100;
    longint n = reduce([] (longint& x, int y) { return x * y; },
                                    range<>(1, N + 1), longint(1));
    cout << sum(map([&n] (int k) { return n.at(k); },
                                range<>(n.length()))) << endl;
}