nayeem2021's blog

Finding the Number of integers in a range which are divisible by some array's at least one element
By nayeem2021, history, 3 years ago, In English

[It's a help seeking post.]

We have an array a of size n(n<=10^5) and a number k(k<=10^10). How can we find the number of integers between 1 to k (including 1 and k) which are divisible by at least one element of a

Example:

10 49 20 30 40 [the array a]

50 [the number k]

Answer

6

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

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

maybe betwen 1 to k instead 1 to n?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe using inclusion-exclusion principle? Not fully sure how but feels like it.

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For the sample isn't the answer 6? Because there's 10, 20, 30, 40, 49, 50

→ Reply