878. 第 n 個神奇數字

思路

題目要求第 $n$ 個神奇數字，神奇數字滿足條件「被 $a$ 整除或 $b$ 整除」。 假設 $n = 100$ ， $a = 2$ ， $b = 3$ ，神奇數字的順序是 $2, 3, 4, 6\dots$ ，那麼可能出現的答案，會落在哪個區間呢？

• $[0, a\times{n}]$ 當中至少存在 $n$ 個神奇數字： $[a, 2a, 3a,\dots, na]$ ，也就是 $[2,4,6,\dots,200]$ 。
• $[0, b\times{n}]$ 當中至少存在 $n$ 個神奇數字： $[b, 2b, 3b,\dots, nb]$ ，也就是 $[3,6,9,\dots,300]$ 。 因此可能的答案範圍落在 $[0, \min(an, bn)]$ 。 後續計算需要扣掉重複計算的部分，也就是兩者的公倍數： $l=\text{lcm}(a,b), [l,2l,3l,\dots]$ ，也就是 $[6,12,18,\dots]$ 。

現在找到兩邊界 $[0, 200]$ ，接下來要透過二分找到答案。

1. 中間點 $mid = 100$ ，那麼 $[0, 100]$ 之間有多少個神奇的數字？

• $a$ 倍數的神奇數字 + $b$ 倍數的神奇數字 - $\text{gcd}(a, b)$ 倍數的神奇數字。
• $\frac{100}{2} + \frac{100}{3}-\frac{100}{6}=\frac{400}{6}=66$ （無條件捨去）

2. $66<100$ ，更新邊界 $[100, 200]$ ， $mid = 150$

• $\frac{150}2+\frac{150}3-\frac{150}6=100$ ，得到第 $n$ 個神奇數字是 $150$ 。

程式碼

二分搜尋 + 容斥原理

class Solution {
private:
    int mygcd(int a, int b) {
        return b == 0 ? a : mygcd(b, a % b);
    }
    int mylcm(int a, int b) {
        return a * b / mygcd(a, b);
    }
public:
    int nthMagicalNumber(int n, int a, int b) {
        const int MOD = 1e9+7;
        int lcm = mylcm(a, b);        
        long long left = 0, right = min(1LL * n * a, 1LL * n * b);
        long long res = 0;
        while(left <= right) { // 二分
            long long mid = left + (right - left) / 2;
            long long cnt = mid / a + mid / b - mid / lcm;
            if(cnt >= n) {
                res = mid;
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return res % MOD;
    }
};

複雜度分析

• 時間複雜度：$O(\log(n))$
• 空間複雜度：$O(1)$