给定长度为 n 的序列 \{a_n\}，共 m 组询问，每次询问一个区间 [l,r] 中，在 \bmod\ k 意义下的最小值。
受不了了根本卡不动
这题我曾经自己编出来过，但只会 \mathcal{O}(n\sqrt{n\log n})。/kk
考虑根号分治。设一个阈值 V，分别考虑 k>V 和 k\le V 的询问。
对于 k\le V 的询问，本质不同的 k 只有 V 种。因此可以将其中 k 相同的拿出来一起做。对于一个固定的 k，设 b_i=a_i\bmod k，使用分块或线段树等 \mathcal{O}(n) 预处理的数据结构进行维护即可。这里的复杂度是 \mathcal{O}(nV+m\log n) 或 \mathcal{O}(nV+m\sqrt{n})。
对于 k>V 的询问，考虑到 a\bmod k=a-ck，所以考虑枚举 k 的倍数 ck，然后寻找一个 a_i 使得 a_i\ge ck 且 a_i - ck 最小。不难发现一个询问会变成 \mathcal{O}(\dfrac{10^5}{V}) 个上述问题。这里需要注意一下空间。
考虑将序列中的元素降序排序，所有询问也降序排序，双指针维护，依次将 \ge k 的元素插入序列，然后询问区间最小值即可完成上述问题。