2015 TCO 1B Easy ModModMod

問題

問題文

自然数 $R$ と自然数の列 $m_0, m_1, \cdots , m_{N-1}$ が与えられる． また， $f(x) = (((x \mod m_0) \mod m_1) … \mod m_{N-1})$ と定義する． $\sum_{i \in [1,R]} f(i) $ は？

方針

$m_i \leq m_{i+1}$ のとき $i$ までの計算結果に $i+1$ 番目の計算を適用しても変化しないので， 見るべき $m$ は狭義減少する場所だけでよい．

$m$ を前から見ていって，今までに見た最小の $m$ で割ったあまりが $a$ になるものの個数を $ c[a] $ にメモしていく．全ての $i (0 \leq i \leq R)$ に対して $c[i] = 1$ である． $m$　が $m'$ に変化すると， $ i<m'$ の場合は $c[i] = c[i+m’] + c[i+2m’] + \cdots$ に， $i \geq m'$ の場合は $c[i] = 0$ となる．

上の図は $m = {7,2}, R = 16$ の場合で，答えは $0 \times 9 + 1 \times 7 = 7$． 図を見れば分かるように，しゃくとり法みたいに遷移するので計算量は $O(N+R)$ となる．

実装

int c[20*1000*1000];

class ModModMod {
public:
    long long findSum( vector <int> m, int R ) {
        rep(i,R+1) c[i] = 1;
        int n = m.size();
        int hi = R+1;
        rep(i,n){
            if(hi < m[i]) continue;
            int nx = m[i];
            for(int j=nx;j<hi;j++){
                c[j%nx] += c[j];
            }
            hi = nx;
        }
        ll ans = 0;
        rep(i,hi) ans += i*c[i];
        return ans;
    }
};