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。

自建示例

公共倍数不重复计数:

输入:n = 5, a = 2, b = 3
输出:8
解释:神奇数依次为 2、3、4、6、8,其中 6 同时是 2 和 3 的倍数但只出现一次,因此第五个是 8。

两个除数完全相同:

输入:n = 4, a = 5, b = 5
输出:20
解释:当 a 与 b 相等时,神奇数就是 5 的正倍数序列 5、10、15、20……;第四个为 20,不会因为同时满足两个相同条件而重复出现。