How many numbers are divisible by at least one element of $S$ 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?
 A: 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}$).
