Zaoly's blog

By Zaoly, history, 15 months ago, In English

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

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it -21 Vote: I do not like it

You could try applying AVX instructions to your brute force code: https://codeforces.me/blog/entry/98594

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    SIMD vectorization is not an optimization on time complexity. I don’t prefer this.

»
15 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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