### Zaoly's blog

By Zaoly, history, 13 months ago,

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$.

• +18

 » 13 months ago, # |   -21 You could try applying AVX instructions to your brute force code: https://mirror.codeforces.com/blog/entry/98594
•  » » 13 months ago, # ^ |   +21 SIMD vectorization is not an optimization on time complexity. I don’t prefer this.
 » 13 months ago, # | ← Rev. 2 →   +10 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)$.