LC.P878[第N个神奇数字]

方法一：容斥原理+二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    private static final int MOD = (int) 1e9 + 7;

    public int nthMagicalNumber(int n, int a, int b) {
        // 最大公倍数
        int c = a * b / gcd(a, b);
        long left = 0, right = (long) Math.min(a, b) * n;
        while (left < right) {
            long mid = left + right >> 1;
            // 容斥原理
            if (mid / a + mid / b - mid / c >= n) right = mid;
            else left = mid + 1;
        }
        return (int) (right % MOD);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
  • 时间复杂度：$O(log(min(a,b) \times n))$
  • 空间复杂度：$O(1)$