0878. Nth Magical Number¶
题目信息¶
- 题号:
0878
- 难度:
Hard
- 主题:
整数、倍数序列、第 n 项
- 原题:
- 重点:
神奇数是能被 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,不会因为同时满足两个相同条件而重复出现。