TCO2015 Round2A Div1 Easy ModModMod

結果

xxx 1286 -> 1275

解けなかったです（unratedと言ったので喜んでいたのですがratedだったみたい）．
おおまかな方針は良かったのですが実装まで落とせませんでした．
writerのソースコードを参考に復習をしました（writerのソースコードとまったく同じになった）．

[Easy: ModModMod ]

問題

整数RとN個の整数の配列mが与えられる．
関数fを次のように定義する．

　　f(x) := (((x mod m[0]) mod m[1]) ... mod m[N-1])

このとき、f(1)+f(2)+...+f(R)を求めよ．
[制約]
1 <= N <= 5000, 1 <= m[i] <= 10000000, 1 <= R <= 10000000

解法

初めに、
　　m[i] < m[i + 1] なら ((x mod m[i]) mod m[i + 1]) = (x mod m[i])
となることが分かります．
したがって、mの先頭から m[i] < m[i + 1] を満たす m[i + 1] を取り除きそれをmmとします．
mmは要素数N'の狭義単調減少列となっています．

x < mm[i-1] のとき f(x) は
　　(((x mod mm[i]) mod mm[i+1]) ... mod mm[N'-1])
と等しくなります．
したがって、mm[i] <= x < mm[i-1] に対して f(x) を求めるときは
　　f(x) = f(x mod mm[i])
を使って値を更新していきます．
f(x)を1からRまで求めて和をとると求める答えになります．
時間計算量は O(R) です．

ソースコード

class ModModMod {

public:
    long long findSum(vector <int> m, int R) {
        vector<int> mm;
        int now = INT_MAX;

        for (auto x : m) {
            if (now > x) {
                now = x;
                mm.emplace_back(x);
            }
        }
        
        vector<int> f(R + 1);
        int idx = mm.size() - 1;

        for (int r = 0, lim = min(mm.back(), R + 1); r < lim; ++r)
            f[r] = r;
        for (int r = mm.back(); r <= R; ++r) {
            if (0 < idx && mm[idx - 1] <= r)
                --idx;
            f[r] = f[r % mm[idx]];
        }

        return accumulate(f.begin(), f.end(), (ll)0);
    }
};