Nth Magical Number (LCM + Binary Search)
Hard · Math & Number Theory · about 30 minutes
Call a positive integer *magical* when a divides it or b divides it. List the magical numbers in increasing order and return the n-th one, modulo 1 000 000 007. (n ≤ 10⁹; a, b ≤ 4·10⁴.)