Finding the Number of integers in a range which are divisible by some array's at least one element

Revision en3, by nayeem2021, 2021-04-03 08:54:50

[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

5

Tags #number theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English nayeem2021 2021-04-03 15:51:12 2 Tiny change: 'swer**\n\n5\n\n\n' -> 'swer**\n\n6\n\n\n'
en3 English nayeem2021 2021-04-03 08:54:50 4
en2 English nayeem2021 2021-04-03 08:51:13 6 Tiny change: 'array a]\n50 [the ' -> 'array a]\n\n50 [the '
en1 English nayeem2021 2021-04-03 08:50:01 429 Initial revision (published)