AOJ 0270 Modular Query - mayoko’s diary

問題

解法

配列 c をソートしておき, 各クエリ q について, c[n-1] から余りを求めていくと考えます。このとき, c[i] を q で割った余りが p であるとすると, c[i]-p から c[i] までの数字は, 余りが p よりも小さいことは明らかなので, わざわざ計算する必要はないです。
よって, c[i] の余りを求めたら, 次に計算すべき値は c[i]-p より小さい数のうち, 配列 c に現れる最も大きな数になります。

これを効率的に計算するために, 前準備として配列 A, T を用意しています。配列 A は n 個の要素の中に c という数があれば true で, そうでなければ false となります。配列 T は, 各数 x について,「x より小さくて, かつ配列 c に含まれている最大の数」を保存しています。

これの計算量は, 各クエリについて $O(n/q)$ で計算できることになるので,全体の計算量は $O(Q \log P)$ となります。 P は入力で与えられる最大の数です。

const int MAXN = 300010;
bool A[MAXN];
int T[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q, ma;
    cin >> N >> Q;
    for (int i = 0; i < N; i++) {
        int c;
        cin >> c;
        A[c] = true;
        ma = max(ma, c);
    }
    int cur = 0;
    for (int i = 0; i < MAXN; i++) {
        T[i] = cur;
        if (A[i]) cur = i;
    }
    while (Q--) {
        int q;
        cin >> q;
        cur = ma;
        int ans = 0;
        while (cur) {
            int amari = cur%q;
            ans = max(ans, amari);
            cur = T[cur-amari];
        }
        cout << ans << endl;
    }
    return 0;
}