Problem statement

https://binarysearch.com/problems/Divisible-Numbers/

Solution

Variation of Leetcode 0878 Nth Magical Number.

Complexity

Total complexity is O(log(N) + log(A + B)), space is O(1).

Code

class Solution:
    def solve(self, n, a, b, c):
        lcm = lambda a, b: a*b//gcd(a, b)
        ab, bc, ac = lcm(a, b), lcm(b, c), lcm(a, c)
        abc = lcm(ab, c)

        beg, end = 0, n * min(a, b, c)
        while beg < end:
            mid = (beg + end)//2
            if mid//a + mid//b + mid//c - mid//ab - mid//bc - mid//ac + mid//abc < n:
                beg = mid + 1
            else:
                end = mid
       
        return beg