AOJ 0270 - Modular Query

問題概要

N個の数字(c₁,c₂,...,c_N)が与えられる。Q個のクエリがあり、各クエリでqが与えられる。このときN個の数字の中でqで割った余りの最大値を出力せよ。

制約

• 2 ≤ N ≤ 300000
• 2 ≤ Q ≤ 100000
• 1 ≤ c_i ≤ 300000
• 1 ≤ q_i ≤ 300000

解法

まず、入力されたN個の数字をc_iの最大の要素数である300000(+1)の配列に埋め込む(この配列は0で初期化)。
例えば、入力例だと、(0-indexedで) 0 0 0 3 0 0 0 0 8 9 0 0 0 ....
のようになる。

次に i > 0 のときに c[i] = max(c[i],c[i-1]) をする。
これは次の埋め込んだ要素が来るまで同じ数字を並べている。
例えば、入力例だと、(0-indexedで) 0 0 0 3 3 3 3 3 8 9 9 9 9 ....
のようになる。

ここである数 x (x>0)を考えると、 x で割った余りが最大になる場合は、
((x-1) + x*k) % x (k = 0,1,2,3,....) の場合であるから、
c[i]についてこの操作を行えば最大の余りを求めることができる。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define M 600001
 
int main(){
  int N,Q,q,in,c[M]={0};
  cin >> N >> Q;
  for(int i = 0 ; i < N ; i++){
    scanf("%d",&in);
    c[in] = in;
  }
  for(int i = 1 ; i < M ; i++){
    c[i] = max(c[i],c[i-1]);
  }
  while(Q--){
    cin >> q;
    int r = 0;
    for(int i = q-1 ; i < M ; i += q){
      r = max(r,c[i]%q);
    }
    printf("%d\n",r);
  }
  return 0;
}