\(a \pmod b\) で \(a\) を \(b\) で割った余りを表すことにします。

小課題

\(\max(A) \leq m\) なら \(a \pmod m = a\) なので、条件を必ず満たすことがわかります。 \(m < \max(A)\) の場合は全探索できるので、 \(O((N+Q)\max(A))\) などで解くことができます。

満点

この問題には \(2\) つの解法があり、それらを組み合わせることで実行時間に間に合わせて解くことができます。

① \(O(\max(A) \log \max(A)+Q \log \max(A))\) 解法

\(m=1,2, \dots ,\max(A)\) に対して、条件を満たすかどうかを調べます。 \(A_i \pmod m \leq \max(A) \pmod m\) を満たす \(i\) の個数が求まれば、それが \(N\) であるかどうかで判定することができます。 \(x \pmod m \leq \max(A) \pmod m\) となる \(x\) は いくつかの区間になっていて、区間の数は \(\max(A)/m\) 個程度なので、\(m=1,2, \dots ,\max(A)\) について足し合わせると合計で \(O(\max(A) \log \max(A))\) 個になります。 \(1\) つの区間に入る \(A_i\) の個数は累積和を用いることで準備 \(O(\max(A))\) ,各クエリ \(O(1)\) で求めることができるので、条件を満たす \(m\) を \(O(\max(A) \log \max(A))\) で求めることができました。

② \(O(N \sqrt{\max(A)\log\max(A)}+Q \log \max(A))\) 解法

まず、 \(\sqrt{\max(A)\log\max(A)}\) 以下の \(m\) について、条件を満たすかどうかを全探索します \(\sqrt{\max(A)\log\max(A)} < m\) の場合を考えます。 \(A_i \pmod m = A_i-m \times B_i\) と書けて、 \(B_i\) は \(\frac{\max(A_i)}{\sqrt{\max(A)\log\max(A)}}\) 以下であることがわかります。 この \(B_i\) が入れ替わるような \(m\) を調べ、そこで区切られた区間ごとに条件を満たす \(m\) の個数を求めていきます。 \(A_i - m \times B_i \leq A_j-m \times B_j\)という式が \(N-1\) 個得られるので、これを満たす \(m\) の最大値を（最小値を管理できる）ヒープなどで管理しておきます。 \(m\) が小さい順から見ていって、 \(B_i\) が更新されるたびに、ヒープを更新していきます（\(A_i\) が \(\max(A)\) に対応するものならヒープをその都度作り直しても間に合います）。 以上で、条件を満たす \(m\) の区間を \(O(N \sqrt{\max(A)\log\max(A)})\) で求めることができました。

まとめ

\(10^4 \leq N\) の場合は①、 \(N < 10^4\) の場合は②を解法として用いると、実行時間に間に合わせて解くことができます。

いずれの解法でも、二分探索することで、各クエリ \(O(\log \max(A))\) で求めることができます。