题目大意：
第 N 个神奇数字
如果正整数可以被 A 或 B 整除，那么它是神奇的。
返回第 N 个神奇数字。由于答案可能非常大，返回它模 10^9 + 7 的结果。
示例 1：
输入：N = 1, A = 2, B = 3 输出：2
示例 2：
输入：N = 4, A = 2, B = 3 输出：6
示例 3：
输入：N = 5, A = 2, B = 4 输出：10
示例 4：
输入：N = 3, A = 6, B = 4 输出：8
提示：
1 <= N <= 10^92 <= A <= 400002 <= B <= 40000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=878
解题思路：
个人感觉，这道题目的表达不是很容易理解，其实通俗易懂点说，可以理解为：有A和B两个正整数，将他们所有不重复的倍数按从小到大进行排列，求出这个序列中的第N个元素。另外这个元素的值可能会非常的大，所以要求返回这个元素与(10^9 + 7)的余数。
先简单说下我刷题的思路，当然这个思路并不仅限于这道题。一般来说，拿到题目后，我习惯先用暴力破解法现将题目解一遍，目的是能够理清解题的最原始思路，在此基础上再来思考如何优化算法。优化算法时，主要考虑的便是如何减少不必要的循环次数，这需要根据题目来进行观察和思考，找到一个或者多个可以优化的方法。
回到本题，暴力算法的思路很简单，分别按顺序算出A和B的倍数，当算到第N个数时结束循环，当前数便是结果。时间复杂度为O(N)，但是看了一眼题目，N的取值范围是10的9次方，也就是最多需要进行10亿次循环，这肯定会超时。所以我们需要优化我们的思路。一起来思考一下：
首先，什么是倍数？任意一个数字A乘以1，2，3，4 …，x，结果都是这个数字的倍数，反过来说，任意一个大于该数字A的数X除以该数字A，得到的结果N就是小于等于X的范围内存在N个A的倍数。
int X = 15; int A = 4; int N = X / A; // N = 3; 15以内存在3个4的倍数(4, 8, 12)
再来考虑两个数字的情况，还以上面的例子来说明，如果A等于4，并且B等于6，那么在15以内存在多少个4和6的倍数呢？同理：
int X = 15; int A = 4; int B = 6; int N1 = X / A; // N = 3; 15以内存在3个4的倍数(4, 8, 12) int N2 = X / B; // N = 2; 15以内存在2个6的倍数(6, 12)
那么问题来了，在小于等于15的范围内，数字4和6都存在相同的倍数12，如何去重？其实这个问题也不复杂，所有重复的数字肯定是A和B的公倍数，因此我们先求出两数的最小公倍数，同理，在小于等于X的范围内，这个最小公倍数的倍数个数便是重复的个数。求最小公倍数的思路不难，从小到大循环A和B中较小一个数字的倍数，如果这个倍数同时也是较大数的倍数，当前数便是最小公倍数。看下代码：
private int findLeastCommonMultiple(int A, int B) {
int index = 1; // 倍
int min = Math.min(A, B); // 小数
int max = Math.max(A, B); // 大数
while (true) {
// 如果小数的index倍大于等于大数，并且小数的index倍也是大数的倍数
if (min * index >= max && min * index % max == 0) {
// 当前小数的index倍便是2数的最小公倍数，返回。
return min * index;
}
index++; // 加一倍继续循环
}
}分析到这里，思路就相对清晰一些了，只要我们能够找到一个数字X，在小于等于X的范围内，分别计算出A的倍数个数N1，B的倍数个数N2，A和B的公约数个数N3，如果：
N == N1 + N2 - N3
即：
if(N == X / A + X / B - X / 最大公倍数) {
return;
}那么，当前数字X就是最后的结果或者说是接近结果的一个数字。为什么说X不一定是结果呢？因为我们在做除法时丢弃了余数，所以当前X并不精确，还是用上面的例子来解释说明一下：比如15以内含有3个4的倍数(4, 8, 12)，但是注意4的第三个倍数并不是15，而应该是12，这一点需要我们在代码中注意。
现在，剩下最后一个问题，如何确定这个X的值？X也是最后的结果，同时他也应该是A的倍数或者B的倍数或者同为两者的倍数。X的取值应该是在A和B中较小的一个数 到 这个较小数与N的乘积范围之间。
Math.min(A, B) <= X <= Math.min(A, B) * N
这个X的范围概念不难理解，我们想要求出A和B所有不重复的倍数中的第N个元素，因为A和B本身也是自己的倍数，所以这个倍数数组的第一个元素肯定是A和B中的较小数。另外，这个数组中的第N个元素肯定要小于等于较小数的第N个倍数。
范围确定了，如何寻找X，显然二分法是最好的方式，令X等于范围中点，将X带入上面的公式，直到结果等于N即可。
if(N == X / A + X / B - X / 最大公倍数) {
return;
}最后来看下全部的代码：
public int nthMagicalNumber(int N, int A, int B) {
long pow = 1000000007;
long maxNum = Math.min(A, B) * (long) N; // 结果的范围上限
long minNum = Math.min(A, B); // 结果的范围下限
long currentNum = (minNum + maxNum) / 2; // 范围中间数
// 计算出A和B的最小公倍数
int leastCommonMultiple = findLeastCommonMultiple(A, B);
while (true) {
// 计算出小于等于currentNum范围内存在多少A和B不重复的倍数count
long count = currentNum / A + currentNum / B - currentNum / leastCommonMultiple;
// 如果count为N，那么当前数为最接近结果的一个数字
if (count == N) {
// 如果currentNum在A和B之间，结果应是currentNum / 小数 * 小数
// 如果currentNum大于A和B，结果应是currentNum / 大数 * 大数
// 第一种情况，currentNum / 大数等于0，所以可以简化为下面的写法
return (int) ((Math.max(currentNum / A * A, currentNum / B * B)) % pow);
}
// 如果count大于N，则需要在currentNum之前继续半分查找
if (count > N) {
maxNum = currentNum;
currentNum = (currentNum + minNum) / 2;
}
// 如果count小于N，则需要在currentNum之后继续半分查找
else {
minNum = currentNum;
// 这里注意一下避免死循环，如果新取得的currentNum与之前的值相同，
// 需要将currentNum 加一
// eg. currentNum = 2, maxNum = 3, (2 + 3) / 2 = 2;
currentNum = (currentNum + maxNum) % 2 == 1 ? (currentNum + maxNum) / 2 + 1 : (currentNum + maxNum) / 2;
}
}
}
// 计算两数的最小公倍数
private int findLeastCommonMultiple(int A, int B) {
int index = 1; // 倍
int min = Math.min(A, B); // 小数
int max = Math.max(A, B); // 大数
while (true) {
// 如果小数的index倍大于等于大数，并且小数的index倍也是大数的倍数
if (min * index >= max && min * index % max == 0) {
// 当前小数的index倍便是2数的最小公倍数，返回。
return min * index;
}
index++; // 加一倍继续循环
}
}本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-878-nth-magical-number解题思路分享/