1317. Divisible By Any of Three
Count how many integers from 1 to n are divisible by a, by b, or by c.
Looping to n is O(n) and too slow at n = 10^9. Counting the three groups and
adding them triple counts anything divisible by more than one.
Inclusion and exclusion fixes that. Add the three, subtract the three overlaps, then add back the middle, which the subtractions removed once too often:
n/a + n/b + n/c
- n/lcm(a,b) - n/lcm(a,c) - n/lcm(b,c)
+ n/lcm(a,b,c)
All divisions are integer divisions, and lcm(x, y) is x / gcd(x, y) * y.
The trap is overflow, and it is the point of this problem. Three bounds of
10^9 multiply to 10^27, which no 64-bit integer holds, so the triple least
common multiple silently wraps and the answer comes out wrong or negative.
A bigger type is not the fix. Notice instead that any multiple greater than n
contributes exactly zero, so cap each least common multiple at n + 1 as soon
as it exceeds n. Every later multiple stays small and the count is unchanged.
Constraints - `1 ≤ n ≤ 1000000000` - `1 ≤ a, b, c ≤ 1000000000`
Input
One line containing four integers n, a, b and c.
Output
Print how many integers from 1 to n are divisible by at least one of a, b and c.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.