困难

问题描述

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n ,a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

示例 1：

输入：n = 1, a = 2, b = 3
输出：2

示例 2：

输入：n = 4, a = 2, b = 3
输出：6

提示：

• 1 <= n <= 109
• 2 <= a, b <= 4 * 104

二分查找

假设 $f(x)$ 为小于等于 $x$ 的神奇数字的个数。

在区间 $[0, x]$ 中，会有 $\lfloor \frac{x}{a} \rfloor$ 个数能被 $a$ 整除，有 $\lfloor \frac{x}{b} \rfloor$ 个数会被 $b$ 整除，某些数同时与 $a$ 和 $b$ 整除，整除个数为 $\lfloor \frac{x}{c} \rfloor$ 个，$c$ 为 $a$ 和 $b$ 的最小公倍数。

根据容斥原理可得 $f(x) = \lfloor \frac{x}{a} \rfloor + \lfloor \frac{x}{b} \rfloor - \lfloor \frac{x}{c} \rfloor$

显然 $f(x)$ 是单调递增的，因此可以使用二分查找找到某个 $x$ 使得 $f(x) = n$。

• 时间复杂度：$O(\log{n \times min(a,b)})$
• 空间复杂度：$O(1)$