0878. Nth Magical Number ======================================================================================================================== 题目信息 -------- :题号: 0878 :难度: Hard :主题: 整数、倍数序列、第 n 项 :原题: `LeetCode 0878 `_ :重点: 神奇数是能被 a 或 b 至少一个整除的正整数,同时被二者整除只在有序序列中出现一次;结果对 10^9+7 取模 题目重述 -------- 给定正整数 ``n``、``a`` 和 ``b``。若一个正整数能被 ``a`` 或 ``b`` 整除,则称它为神奇数。 把所有神奇数按严格递增顺序排列,能同时被 ``a`` 和 ``b`` 整除的数也只作为一个整数出现。请返回第 ``n`` 个神奇数对 ``10^9 + 7`` 取模后的结果;``n`` 从 ``1`` 开始计数。 ``1 <= n <= 10^9``,``2 <= a, b <= 4 * 10^4``。 自建示例 -------- 公共倍数不重复计数: .. code-block:: text 输入:n = 5, a = 2, b = 3 输出:8 解释:神奇数依次为 2、3、4、6、8,其中 6 同时是 2 和 3 的倍数但只出现一次,因此第五个是 8。 两个除数完全相同: .. code-block:: text 输入:n = 4, a = 5, b = 5 输出:20 解释:当 a 与 b 相等时,神奇数就是 5 的正倍数序列 5、10、15、20……;第四个为 20,不会因为同时满足两个相同条件而重复出现。