One Possible Approach may be,

Sort the Array $$$A$$$ For every $$$i$$$, you iterate over all it's multiples $$$x, x \le 2max(A)$$$, and find the maximum $$$a_i \lt x$$$. This should have the same complexity as of Sieve, i.e $$$M\log M$$$ with $$$M = max(m)$$$.

However for this the limits should be $$$a_i,m \leq 10^6.$$$

You may want to try 484B - Maximum Value

Problem link please. We don't want to be helping cheaters. So please provide a link to your question.

nevermind

Say M is max possible m. Then there's $$$O(n\log{n} + n\sqrt{M} + q\sqrt{M}\log{n})$$$ solution. For each $$$m \lt \sqrt{M}$$$ calculate the answer naively, that takes $$$O(n\sqrt{M})$$$. Then sort the array to anwer other queries. For other m decompose the array into segments such that for each segment $$$l ... r$$$ $$$\lfloor{}\frac{a_l}{m}\rfloor{} = \lfloor{}\frac{a_{l+1}}{m}\rfloor{} = ... = \lfloor{}\frac{a_r}{m}\rfloor{}$$$. The answer is $$$max(a_r\mod{m})$$$ for each right boundary of each segment. There are $$$O(\sqrt{M})$$$, but i don't know if there's a way to decompose the array faster than $$$O(\sqrt{M}\log{n})$$$

I have $$$O(n + q + M\cdot log(M))$$$ solution where $$$M$$$ is maximum over all m.

For each $$$1 \le m \le M$$$ calculate answer. Every number $$$x$$$ can be written as $$$x = y \cdot m + r$$$, where $$$y = \lfloor \frac{x}{m} \rfloor$$$ and module remainder $$$r \lt m$$$. Iterate over all $$$m$$$ and $$$y$$$ ($$$1 \le m \le M, 0 \le y \le \lfloor \frac{M}{m} \rfloor$$$). Now find maximum $$$a[i] \lt y \cdot m + m$$$ and update answer for $$$m$$$ as $$$a[i]$$$ % $$$m$$$ (you need store result for fast search maximum $$$a[i]$$$). Time complexity is $$$O(\sum_{m=1}^{M}\frac{M}{m}) = O(M\cdot log(M))$$$ (harmonic series).