入门力扣自学笔记203 C++ （题目编号：878）

878. 第 N 个神奇数字

题目：

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

---

示例 1：

输入：n = 1, a = 2, b = 3
输出：2

---

示例 2：

输入：n = 4, a = 2, b = 3
输出：6

---

提示：

1 <= n <= 109
2 <= a, b <= 4 * 104

---

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/nth-magical-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：

本题采用二分法，下限位a和b的最小值，上限就是n×a和b的最小值。

首先，我们先要找到a和b的最小公倍数。

其次，我们发现这个过程中，a和b有重复的数字，所以能够被整除他们的数字为x/a+x/b-x/c，这里的c是最小公倍数，减去的主要原因是找到他们有多少个重复的数字，并将这个减去，得到的就是有多少个能够整除的数字。

最后，只要不断控制左右限，利用二分法就能找到最后的数字了。   

---

代码：

class Solution {
public:
    const int mod = 1e9+7;
    int nthMagicalNumber(int n, int a, int b) {
        long long left = min(a , b);
        long long right = (long long)n * min(a ,b);
        int c = lcm(a , b);
        while(left <= right)
        {
            long long mid = (left + right) / 2;
            long long cnt = mid / a + mid / b - mid / c;
            if(cnt >= n)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return (right + 1) % mod;
    }
};

也可以用枚举，但是枚举时间会超！！！

class Solution {
public:
    const int c = 1e9+7;
    int nthMagicalNumber(int n, int a, int b) {
        int place = 0;
        int num = 2;
        while(1)
        {
            if(num % a == 0 || num % b == 0)
            {
                place ++;
                if(place == n)
                    break;
                num ++ ;
            }
        }
        return (num % c);
    }
};

---

注：

1.gcd函数和lcm函数

最大公因数（英语：highest common factor，hcf）也称最大公约数（英语：greatest common divisor，gcd）是数学词汇，指能够整除多个整数的最大正整数。而多个整数不能都为零。例如8和12的最大公因数为4。

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数（Least Common Multiple，简写为 lcm）。

 最小公倍数=两数乘积/最大公约数