1410. Divisible by at Least One of Them
For each query count the integers x with L <= x <= R that are divisible by
at least one of the given values d[0] ... d[n-1].
L = 1, R = 20, d = 3 5
multiples of 3: 3 6 9 12 15 18
multiples of 5: 5 10 15 20
15 is in both, so the count is 6 + 4 - 1 = 9
## What most people try first
Add the counts: floor(R/d[0]) + floor(R/d[1]) + ... minus the same at
L - 1. That double counts every x divisible by two of the values, triple
counts those divisible by three, and so on. Looping over the range instead is
impossible, since R reaches 10^18.
Problem 1317 answers the same question for exactly three fixed divisors, where
the seven terms can be written out by hand. Here n reaches 10, so the terms
have to be generated.
## Inclusion and exclusion over the subsets
A value is divisible by every member of a set of divisors exactly when it is
divisible by their least common multiple. So, writing M(S) for the lcm of
a subset S and C(v) for the count of multiples of v in [L, R]:
answer = sum over non-empty S of (-1)^(|S| - 1) * C(M(S))
With n at 10 that is 1023 subsets, each needing an lcm of at most 10 values,
and C(v) = floor(R/v) - floor((L-1)/v) from problem 1409. Since L >= 1
here, both divisions have non-negative operands, so the flooring question of
the previous problems does not arise.
## Why it is correct
Fix an x in the range and let T be the set of indices whose divisor divides
x. If T is empty, x contributes to no term. If T is non-empty with
|T| = m, then x is counted by C(M(S)) exactly for the subsets S
contained in T, and a subset of size j carries the sign (-1)^(j-1). So
the total contribution of x is
sum over j = 1..m of C(m, j) * (-1)^(j-1) = 1 - (1 - 1)^m = 1
by the binomial theorem. Every x divisible by something contributes exactly
1 and every other x contributes 0, which is the count asked for.
## The boundary that breaks a careless implementation
The lcm of ten values near 10^18 is about 10^180. It must therefore
never be formed, in any width. The lcm is built one divisor at a time as
v = v / gcd(v, d) * d, dividing before multiplying, and before each multiply
the guard is a division:
step = d / gcd(v, d)
if v > R / step: this subset contributes 0, stop
v = v * step
That is sound because L >= 1, so if the lcm exceeds R then its smallest
positive multiple already exceeds R and the count really is 0. The guard
also has to come before the multiply, not after: checking afterwards means the
overflow has already happened and the wrapped value can look small.
Duplicate divisors are allowed and need no special handling, since the lcm of a value with itself is itself.
## Overflow
R and each d[i] reach 10^18, so every count and the running total need
64 bits; a 32-bit build answers 0 where the truth is 733333333333333334,
because it cannot hold R. The lcm is capped as described, and v / gcd(v, d) * d with
the division first keeps the partial product at or below R. In JavaScript all
of this is past 2^53, so BigInt is used, with one exception: the subset mask
stays a plain Number, because a bitwise operator applied to a BigInt-sized
value would truncate to 32 bits.
## Cost
O(q * 2^n * n * log d).
Constraints - `1 ≤ q ≤ 100` - `1 ≤ L ≤ R ≤ 1000000000000000000` - `1 ≤ n ≤ 10` - `1 ≤ d[i] ≤ 1000000000000000000`, and the `d[i]` need not be distinct
Input
The first line contains q.
Each query is two lines: the first has L, R and n, and the second has the
n divisors.
Output
For each query print the count, one per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.