Project Euler 26

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

本来オイラーの定理など数学を使えば速く解ける問題だが、題意通りに書いても十分速く答えが出る。

itertools.h

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

using namespace std;
using namespace itertools;

class cDec {
    int d;
    int r;
    
public:
    cDec(int d) : d(d), r(1) { }
    int next() {
        int prev = r;
        r = r * 10 % d;
        return prev;
    }
    bool exists_next() { return true; }
};

int cycle(int n) {
    vector<int> v(n, 0);
    return snd(head(filter([&v] (tuple<int,int> x)
                { return fst(x) != snd(x); },
                map([&v] (tuple<int,int> y) -> tuple<int,int>
                    { int prev = v[snd(y)]; v[snd(y)] = fst(y);
                        return make_tuple(fst(y), fst(y) - prev); },
                zip(itertools::count<>(1), cDec(n))))));
}

tuple<int,int> longer(tuple<int,int> x, tuple<int,int> y) {
    return snd(x) >= snd(y) ? x : y;
}

int main() {
    const int   N = 1000;
    cout << fst(reduce1(longer, map([] (int d)
                    { return make_tuple(d, cycle(d)); },
                    range<>(1, N)))) << endl;
}