You are given 4 integers X, Y, L, R. You need to find the number of integers between L and R inclusive that is divisible by any of the two numbers X or Y.
How to find the answer without trying all numbers between L and R.
I know we will use the inclusion-exclusion principle but I can't come up with the solution.
Define S(n,d) as the set of positive integers up to and including n that are divisible by d. This set has size n/d (rounded down).
The set of integers divisible by X or Y is the union of two such sets. This is where subtracting the intersection comes in, to avoid double counting, giving a set S(n, X or Y) of numbers divisible by X or Y.
To deal with a range take a difference: S(R, X or Y) - S(L-1, X or Y)