求含恰好2个置位比特的序列第N项的优化解法（原代码超时）

问题本质分析 #

首先要明确：这个序列里的每个数，都是二进制表示中恰好有两个1的正整数，按数值从小到大排列。这类数可以统一表示为 (2^k + 2^m)（其中 (k > m \geq 0)），排序规则等价于先按高位k从小到大，再按低位m从小到大排列。

你的原始代码用嵌套循环逐个计数，时间复杂度是 (O(\sqrt{N})) 每测试用例，当N=1e14时，单例就要遍历上千万次，1e5个测试用例根本不可能在时间限制内完成。我们需要用组合数学+二分查找的方式，把时间复杂度降到 (O(\log N)) 每测试用例，完美适配大输入范围。

核心推导步骤 #

1. 定位高位k
   从0到k-1的位中选两个不同位的组合数是 (C(k,2) = \frac{k*(k-1)}{2})，这个数代表了所有高位小于k的符合条件的数的总个数。我们需要找到最大的k，使得 (C(k,2) < N)——这意味着第N项的高位就是k。

   可以通过二次不等式近似估算k的范围（(k \approx \sqrt{2N})），再用二分查找精确确定k，这样比直接遍历快得多。

2. 定位低位m
   找到k之后，计算剩余的位置偏移量：(offset = N - C(k,2))，由于m从0开始计数，所以低位m就是 (offset - 1)。

3. 计算最终结果
   结果就是 (2^k + 2^m)，由于k可能很大（比如N=1e14时，k≈1.4e7），必须用BigInteger来处理大数运算，避免溢出。

优化后的Java代码 #

import java.math.BigInteger;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        while (testCases-- > 0) {
            long n = sc.nextLong();
            
            // 先通过倍增找到k的上界，避免二分范围过大
            long k = 1;
            while (true) {
                BigInteger comb;
                if (k <= 1000000) { // 小数值直接用long计算，更快
                    comb = BigInteger.valueOf(k * (k - 1) / 2);
                } else {
                    BigInteger bigK = BigInteger.valueOf(k);
                    comb = bigK.multiply(bigK.subtract(BigInteger.ONE)).divide(BigInteger.TWO);
                }
                if (comb.compareTo(BigInteger.valueOf(n)) >= 0) {
                    break;
                }
                k *= 2;
            }
            
            // 二分查找最大的k，使得C(k,2) < n
            long left = 1, right = k;
            long bestK = 0;
            while (left <= right) {
                long mid = left + (right - left) / 2;
                BigInteger comb;
                if (mid <= 1000000) {
                    comb = BigInteger.valueOf(mid * (mid - 1) / 2);
                } else {
                    BigInteger bigMid = BigInteger.valueOf(mid);
                    comb = bigMid.multiply(bigMid.subtract(BigInteger.ONE)).divide(BigInteger.TWO);
                }
                int cmp = comb.compareTo(BigInteger.valueOf(n));
                if (cmp < 0) {
                    bestK = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            // 计算偏移量和低位m
            BigInteger combBest = BigInteger.valueOf(bestK)
                    .multiply(BigInteger.valueOf(bestK).subtract(BigInteger.ONE))
                    .divide(BigInteger.TWO);
            long offset = n - combBest.longValue();
            long m = offset - 1;
            
            // 计算2^bestK + 2^m
            BigInteger result = BigInteger.ONE.shiftLeft((int) bestK)
                    .add(BigInteger.ONE.shiftLeft((int) m));
            System.out.println(result);
        }
        sc.close();
    }
}

代码细节说明 #

• 倍增+二分查找：先通过倍增快速缩小k的范围，再用二分查找精确命中，确保每步都是对数级别的时间消耗。
• 混合数值处理：小数值用long计算提升速度，大数值用BigInteger避免溢出，兼顾效率和正确性。
• 大数运算：用BigInteger.shiftLeft()计算2的幂次，比直接用pow()更高效，而且能处理超大的指数。

内容的提问来源于stack exchange，提问作者Raghunath Rao