読者です 読者をやめる 読者になる 読者になる

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);
    }
};