これ好き！楽しい！！

問題概要

長さ $N$ の数列 $a_{1}, \dots, a_{N}$ で定義される、全 $N$ ステップの操作が与えられる。操作は整数 $x$ に対して行うものであり、 $i$ 回目の操作は次のものである:

$x$ を $x$ % $A_{i}$ で置き換える

$M$ 個の整数 $b_{1}, \dots, b_{M}$ それぞれに対して $N$ ステップの操作を行って得られる結果を答えよ。

制約

$1 \le N, M \le 10^{5}$

考えたこと

愚直にやると $O(NM)$ となって間に合わない。工夫が必要になる。ここで注目したいことは、たとえば $3$ で割ったあとに、 $7$ で割っても値は変わらない。一般に、 $p \lt q$ であるとき、

$x$ % $p$ は最初から $q$ 未満なので、% $q$ をしても値は変化しない

ということになる。よって、数列 $A$ において、 $A_{i} \lt A_{j}$ ( $i \lt j$ ) となっている部分はあらかじめ削除することができる。よって数列 $A$ は単調減少であるものと考えてよい！！

そうとわかれば二分探索

そうとわかれば、数列 $A$ による操作を効率化できる。具体的には、たとえば $A = (10, 9, 5, 2)$ に対して $x = 28$ を適用するとき

まず 28 % 10 = 8 となる
数列 A において、最初に 8 以下となる箇所を探す (5)
8 % 5 = 3 となる
数列 A において、最初に 3 以下となる箇所を探す (2)
3 % 2 = 1 となる
数列 A において、最初に 1 以下となる箇所を探す (なし)
よって答えは 1

というように考えることができる。つまり以下のことを繰り返せば OK。

数列 $A$ において、最初に $x$ 以下となる箇所 $A_{i}$ を二分探索によって探す
$x$ を $x$ % $A_{i}$ で置き換える

これによって毎回のステップで $x$ の値はかならず半分以下になるので高々 $O(\log{x})$ 回のステップで処理が終わる！

まとめると計算量は $O(M \log{N} \log {\max(b_{1}, \dots, b_{M})})$ となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<long long> a({1LL<<60}), b(M);
    for (int i = 0; i < N; ++i) {
        long long v;
        cin >> v;
        if (a.back() > v) a.push_back(v);
    }
    for (int i = 0; i < M; ++i) cin >> b[i];
    reverse(a.begin(), a.end());

    for (int i = 0; i < M; ++i) {
        if (i) cout << " ";
        long long res = b[i];
        int it = (int)a.size() - 1;
        while (it > 0) {
            it = upper_bound(a.begin(), a.end(), res) - a.begin();
            if (it == 0) break;
            --it;
            res %= a[it];
        }
        cout << res;
    }
    cout << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3189 Mod Rush (HUPC 2020 day3-E)

問題概要

制約

考えたこと

そうとわかれば二分探索