如果正整数可以被 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^9
    2 <= A <= 40000
    2 <= B <= 40000

    1. class Solution {
    2.     int mod = (int)1e9 + 7;
    3.     public int nthMagicalNumber(int n, int a, int b) {
    4.         //求最小公倍数为 (a * b) / gcd(a, b)
    5.         int common = a / gcd(a, b) * b;
    6.         //为什么是1e15, 因为为右边界最大为n * a
    7.         long l = 0, r = (long)1e15;
    8.         while (l < r) {
    9.             long mid = l + r >> 1;
    10.             //求能被a整除的个数为 mid / a
    11.             if (mid / a + mid / b - mid / common >= n) r = mid;
    12.             else l = mid + 1;
    13.         }
    14.         return (int)(l % mod);
    15.     }
    16.     private int gcd(int a, int b) {
    17.         if (a == 0) return b;
    18.         return gcd(b % a, a);
    19.     }
    20. }