Is there any algorithm to solve the following problem within several seconds? If not, what if $$$1 \le a_i \le 10^9$$$, $$$1 \le b \le 10^9$$$?
You are given an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$. Then you should process $$$q$$$ queries. In each query, you are given an integer $$$b$$$. How many elements of the array $$$a$$$ are the factors of $$$b$$$?
We say $$$a$$$ is a factor of $$$b$$$, if and only if there exists an integer $$$c$$$ such that $$$a \cdot c = b$$$.
Constraints: $$$1 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$, $$$1 \le a_i \le 10^{18}$$$, $$$1 \le b \le 10^{18}$$$.
For example, $$$n = 3$$$, $$$a = \{ 4, 6, 17 \}$$$, $$$q = 4$$$:
- $$$b = 12$$$, answer is $$$2$$$.
- $$$b = 34$$$, answer is $$$1$$$.
- $$$b = 102$$$, answer is $$$2$$$.
- $$$b = 40800$$$, answer is $$$3$$$.
You could try applying AVX instructions to your brute force code: https://mirror.codeforces.com/blog/entry/98594
SIMD vectorization is not an optimization on time complexity. I don’t prefer this.
This could be solved if you work with smaller numbers and have range queries. If your sequence is made out of different numbers, which are less than $$$10^6$$$, you can store all the positions $$$idx$$$, for which $$$a_{idx}$$$ is a factor of $$$d$$$ in the vector $$$f_d$$$. Then, after receiving a query, you can do two binary searches in $$$f_b$$$, so you know how many factors of $$$b$$$ are in $$$[l,r]$$$. When numbers are different, you will get a complexity $$$O(MAX\ log\ MAX + (N + Q)\ log\ N)$$$.