Zaoly's blog

Is There Any Fast Algorithm to Count Given Integer’s Factors in Array?
By Zaoly, history, 16 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

»
16 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

→ Reply
  • »
    »
    16 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.

    → Reply
»
16 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)$$$.

→ Reply