How many numbers are divisible by at least one element of $S$

Question

I have a set S containing $N$ $(1 \le N \le 20)$ integers $a_i$ $(1 \le a_i \le 10^{18})$ and two numbers $a$ and $b$. I want to tell how many numbers between $a$ and $b$ are divisible by at least one of the numbers from set S. I can do it in $O(2^n \cdot n)$ time using inclusion-exclusion principle. Is there any faster way to do this?

Answer 1

If $a$ and $b$ are very large numbers, then you can use the following. I will assume that the $a_i$'s are relatively prime (to simplify).

Let $c=\prod_{i=1}^Na_i$.

Then, the number of integers less than $c$ which are divisible by $a_1$ is $\prod_{i=2}^Na_i$, the number of integers less than $c$ which are divisible by $a_1$ and $a_2$ is $\prod_{i=3}^Na_i$.

In general, using the inclusion/exclusion principle, we know that the number of integers relatively prime to $a_1,\cdots,a_n$ is given by (where $S=\{1,\cdots,N\}$)

$$ \prod_{i=1}^Na_i-\sum_{A\subseteq S,|A|=|S|-1}\prod_{i\in S}a_i+\sum_{A\subseteq S,|A|=|S|-2}\prod_{i\in S}a_i-\sum_{A\subseteq S,|A|=|S|-3}\prod_{i\in S}a_i+\cdots+(-1)^N $$

These are the coefficients of the polynomial $\prod(a_i-x)$. So, then, we can calculate the number of integers less than or equal to $c$ relatively prime to the $a_i$'s by substituting $1$ for $x$ and multiplying which takes $O(N)$.

In fact, any sequence of integers of length $c$ will have exactly this many integers relatively prime to the $a_i$'s. So, you could calculate the number of integers less than $m$ which are relatively prime to the $a_i$'s where $1\leq m\leq c\leq 10^{360}$ and break up the interval between $b$ and $a$ into blocks of size $c$ and use a table to look up the rest.

This can give an algorithm that is around $O(N)$ (around because I'm ignoring bit complexity of multiplication) - but the constant is HUGE (at least $10^{360}$).