class="markdown_views prism-atelier-sulphurpool-light">

问题描述：

878. 第 N 个神奇数字
如果正整数可以被 A 或 B 整除，那么它是神奇的。 返回第 N 个神奇数字。由于答案可能非常大，返回它模 10^9 + 7 的结果。 示例 1：

输入：N = 1, A = 2, B = 3
输出：2

提示：

• 1 <= N <= 10^9
• 2 <= A <= 40000
• 2 <= B <= 40000

问题分析：

这个题目，应该有一半是数学问题，不易想到。先简单介绍一下容斥原理，我们要求两个集合的并集，可以先把两个单集合相加，然后减去他们的交集就可以（网上有大把，可以参考哦，这里只是简单一提）。
（1）返回第 N 个神奇数字？很显然，这个神奇数字里面应该包含N个数字可以被 A 或 B 整除（这里的包含可以理解为神奇数字前面的数字，不太严谨哈）。
（2）现在，我们可以设置两个界限，一个最小下界 0，一个最大上界10**15。
（3）在两个上下界限内，进行二分查找，看看哪数字合适。
（4）如何确定这个神奇数字包含的个数？有数学方法可以求出来，简单理解就是求出这个神奇数字的能被A整除的个数+被B整除的个数-能同时被A、B整除的个数 （也就用到容斥原理，具体的可以去网上深入学习哦），即可。

Python3实习：

# @Time :2018/08/07 # @Author :LiuYinxing # 二分查找 class Solution: def nthMagicalNumber(self, N, A, B): def gcd(x, y): # 求两个数的最小公约数 return x if not y else gcd(y, x % y) # 辗转取余法 mod = 10**9 + 7 L = A // gcd(A, B) * B # 获取能同时被 A，B 整除的信息 L def magic_below_n(n): # 返回能整数 n包含 能被 A 或 B 整除的数个数 return n // A + n // B - n // L # n // A 表示能被A整除的数， n // B 表示能被B整除的数 n // L 表示能同时被A 或 B 整除的数个数 low, high = 0, 10**15 # 初始化上下界 while low < high: # 进行二分查找 mid = (low + high) // 2 if magic_below_n(mid) < N: low = mid + 1 else: high = mid return low % mod # 取模 if __name__ == '__main__': N, A, B = 3, 6, 4 solu = Solution() print(solu.nthMagicalNumber(N, A, B)) 欢迎指正哦。 参考链接：
[1]： leetcode.com/problems/nth-magical-number/solution/