题解

思路

令 $n=\max(Q,\max B_i)$。

做法

在前 $2n$ 个质数中，一个质数只有在某次 $A_i$ 恰等于它时才会被删除，所以至多删掉 $Q$ 个，仍至少留下 $B_i$ 个；因此答案不超过第 200000 个质数 $2750159$。只需维护这个有限区间。

树状数组初始把每个位置记为 1。每个不同的 $A_i$ 只处理一次，扫描其不超过上界的倍数，若尚未删除就置零并更新树状数组；随后用树状数组二进制下降找到第 $B_i$ 个 1。

复杂度

重复值直接跳过，倍数扫描总量满足调和级数界，整体时间约为 $O(U\log U+Q\log U)$，空间为 $O(U)$，其中 $U=2750159$。