TCO15 Round 2A easy:ModModMod

TCO15 Round 2Aに参加。遅いながらもなんとかeasy通して140ptくらいゲットしました。unratedで悲しいですね。

問題

ある数列mが与えられて,f(x)=x%m[0]%m[1]%m[2]...と定義する。
ある整数Rについて,f(1)+f(2)+...+f(R)の値はいくらか。

解法

f(x)の結果としてpという値を取るものが1〜Rの中にいくつあるかを考える。これがわかれば,求める答えもわかる。じゃあどうやれば良いのか？

何とも割っていない時は
p[1] = 1
p[2] = 1
...
p[R] = 1
である。m[0]で割った余りを考えると,この時はm[0]以上の値のみ考えれば良い。すると,
p[0] = a0
p[1] = a1
...
p[m[0]-1] = am
と言うように,pのインデックスの取りうる値は,0〜m[0]-1の間に収まる。次にm[1] < m[0]とすると,今度はm[1]〜m[0]-1の間の値のみ考えれば良く,pのインデックスの取りうる値は0〜m[1]-1に収まる。このように,結局新しいm[i]が出てきた際に考慮すべき範囲が
m[0]〜R
m[1]〜m[0]
...
m[n]〜m[n-1]
というようになって最悪でも扱う範囲が0〜Rに収まるので,計算量O(R)で処理できる。

const int MAXN = 10010000;
ll memo[MAXN];

class ModModMod {
public:
    long long findSum(vector <int> m, int R) {
        for (int i = 1; i <= R; i++) {
            memo[i] = 1;
        }
        int cur = MAXN;
        for (int el : m) {
            if (cur > el) {
                for (int i = el; i < cur; i++) {
                    memo[i%el] += memo[i];
                    memo[i] = 0;
                }
                cur = el;
            }
        }
        ll ans = 0;
        for (int i = 0; i < cur; i++) ans += (ll)i*memo[i];
        return ans;
    }
};