1417. The Chance It Divides, as an Exact Fraction

An integer is chosen uniformly at random from [L, R]. For each query print the probability that it is divisible by at least one of the given values d[0] ... d[n-1], as an exact reduced fraction.

L = 1, R = 20, d = 3 5 qualifying: 3 5 6 9 10 12 15 18 20 nine of the twenty answer: 9/20

The answer is a fraction, not a decimal. A probability is almost never exactly representable in binary, so printing 0.45 would need a tolerance, and a problem that needs a tolerance does not belong in this topic. Printing the reduced fraction makes the answer a single exact value that all five reference languages agree on to the last digit.

## The sign rule, pinned before anything is asserted

A fraction has more than one reduced spelling unless the sign is placed by a rule: -1/2 and 1/-2 are the same number. So this problem requires

• the denominator positive,
• the sign carried by the numerator,
• zero written exactly 0/1.

Without that sentence the five reference languages would disagree and the problem would be unanswerable rather than hard.

Since the numerator here is a count and the denominator a width, both are non-negative, so the rule only has to settle 0, which prints 0/1.

## What most people try first

Count the qualifying values by looping over the range. R reaches 10^18, so that is impossible. The second attempt adds the individual counts floor(R/d[i]) - floor((L-1)/d[i]), which double counts every value divisible by two of the divisors.

## Count by inclusion and exclusion, then reduce once

This is problem 1410 followed by one reduction. A value is divisible by every member of a subset exactly when it is divisible by their least common multiple, so

numerator = sum over non-empty S of (-1)^(|S|-1) * C(lcm(S)) denominator = R - L + 1

where C(v) = floor(R/v) - floor((L-1)/v). Then divide both by their gcd.

## Why it is correct

For a value divisible by exactly m of the divisors, the subsets of those m contribute C(m,1) - C(m,2) + ... = 1 - (1-1)^m = 1, so each qualifying value is counted exactly once and each other value zero times. That is the count. Dividing by the number of equally likely outcomes is the definition of a uniform probability, and reducing by the gcd is the argument of problem 1414.

The probability is therefore a rational number whose denominator divides R - L + 1, which is why an exact answer always exists and why no tolerance is needed.

## The boundary that breaks a careless implementation

The lcm of ten values near 10^18 is about 10^180 and must never be formed. Build it one divisor at a time as v / gcd(v, d) * d, dividing first, and guard with a division before each multiply: if v > R / step the subset's lcm exceeds R, so it has no multiple in [1, R] and the term is 0. The guard is sound only because L >= 1; with 0 in the range, 0 is a multiple of every lcm however large.

A divisor of 1 is allowed, and it makes the answer 1/1 since 1 divides everything.

## Overflow

R reaches 10^18, so the counts, the numerator and the denominator all need 64 bits: a 32-bit build answers 0/1 where the truth is 366666666666666667/500000000000000000, and in the one-divisor case it answers -1/1486618624 where the truth is 1/1000000000000000000. The reduction itself cannot overflow, since Euclid only takes remainders and the final divisions shrink both values. In JavaScript every quantity is past 2^53, so BigInt is required.

## 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