A long fence has a post at every integer position; the gate is at position 0, posts to the
left have negative positions. Two painters work on the stretch from lo to hi (both included):
- the red painter paints every post whose position is a multiple of
a, - the blue painter paints every post whose position is a multiple of
b.
A post painted by both turns purple. Write fence(lo, hi, a, b) that returns a tuple
(red_only, blue_only, purple): how many posts in the stretch end up red only, blue only and
purple. Remember that 0 is a multiple of every number.
Examples
Input: lo = 1, hi = 20, a = 4, b = 6
Output: (4, 2, 1)
Explanation: red 4, 8, 16, 20; blue 6, 18; purple 12.
Input: lo = -6, hi = 6, a = 2, b = 3
Output: (4, 2, 3)
Explanation: purple posts are -6, 0 and 6.
Input: lo = 5, hi = 5, a = 7, b = 7
Output: (0, 0, 0)
Constraints
-10**18 <= lo <= hi <= 10**181 <= a, b <= 10**18
Goals
- Count multiples in a range that may contain negative numbers
- Use gcd to find the lcm
- Split a count into overlapping and non-overlapping parts