题目链接

小q的数列

题目描述

一个数列 定义如下：

给定一个整数 ，你需要求出 的值，以及使函数值等于 的最小的非负整数参数 是多少。

解题思路

本题包含两个子问题：一是求函数值 ，二是求满足 的最小 。问题的关键在于理解递推公式 的本质。

  1. 分析 的含义

    递推公式为 。我们将其与二进制运算联系起来：

    • 等价于将 的二进制表示右移一位（x >> 1）。

    • 等价于取 的二进制表示的最低位（x & 1）。

    • 根据题目的初始条件，，所以 的值恰好就等于 。

    因此，递推关系可以被理解为：。 如果我们将这个过程递归地展开，我们会发现 实际上是在不断地剥离 的二进制最低位并将其累加起来。这个过程最终的结果是 的二进制表示中所有位的数字之和，即** 的值等于 的二进制表示中 1 的个数**（也称作“population count”或“汉明权重”）。

  2. 求解

    知道了 的含义后，求解就变得非常简单。我们只需要统计整数 的二进制表示中有多少个 1。大多数编程语言都提供了高效的内置函数来完成这个任务。

  3. 求解最小的

    第二个子问题是找到最小的非负整数 ，使得 。 设 ，问题就转化为：找到最小的非负整数 ，使得 的二进制表示中含有 个 1。

    要想让一个正整数在含有固定数量的 1 的前提下值最小，我们必须将这些 1 放在尽可能低的二进制位上。 例如，如果需要 个 1，那么最小的数其二进制表示应为 ...00111。

    因此，这个最小的数 的二进制表示就是 个 1。它的值为：

    这是一个等比数列求和，结果为 。 这个公式对于 （即 ）也成立，此时 。

    总结算法：

    1. 对于给定的 ，计算其二进制中 1 的个数，记为 。

    2. 的值就是 。

    3. 最小的 的值为 。

代码

#include <iostream>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long x;
        cin >> x;
        long long v = __builtin_popcountll(x);
        long long k = (1LL << v) - 1;
        cout << v << " " << k << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long x = sc.nextLong();
            int v = Long.bitCount(x);
            long k = (1L << v) - 1;
            System.out.println(v + " " + k);
        }
    }
}

def main():
    T = int(input())
    for _ in range(T):
        x = int(input())
        v = bin(x).count('1')
        k = (1 << v) - 1
        print(v, k)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：位运算

  • 时间复杂度：对于每次查询，计算 popcount 和 都是非常快的操作。如果使用内置函数，可以认为是 或者常数时间（取决于具体实现）。对于 组查询，总时间复杂度为 。

  • 空间复杂度：。算法只需要常数空间来存储变量。