解题思路

我们把“兑换”过程视为一棵二叉树：每次把一张面额为 x>1 的钞票拆成 ⌊x/2⌋、x mod 2、⌊x/2⌋，其中当且仅当 x 为偶数时会产生一张 0。因此，问题等价于：整棵树里一共分裂了多少次“偶数面额”的节点。

设答案为 f(n)。直接递推可得

• f(0)=f(1)=0

• n>1 时：

  • 若 n 为偶数：f(n) = 2*f(n/2) + 1（本次分裂产生 1 个 0，两张 n/2 继续分裂）
  • 若 n 为奇数：f(n) = 2*f(⌊n/2⌋)（本次分裂不产生 0）

进一步观察层次结构：第 d 层共有 2^d 张面额为 ⌊n/2^d⌋ 的钞票。若 ⌊n/2^d⌋ 为偶数，就会在该层产生 2^d 个 0。 把 n 写成二进制，记最低位为第 0 位。可以发现：

• ⌊n/2^d⌋ 的奇偶性正由二进制的第 d 位决定：该位为 0 则偶，为 1 则奇；
• 有效层数为 d=0…L-1，其中 L = ⌊log₂ n⌋（最高位下标）。

于是

结论： 令 msb = 2^{⌊log₂ n⌋}（不超过 n 的最大 2 的幂），则

该式 O(1) 计算，适用于 n ≤ 10^{18}。

复杂度分析

• 时间复杂度：每组样例 O(1)（只需找最高位的 2 的幂并做几次常数运算）。
• 空间复杂度：O(1)。

代码实现

Python

# 中文注释版
import sys

def zeros_count(n: int) -> int:
    """
    计算最终产生的 0 的数量
    利用闭式公式：f(n) = 2*msb - 1 - n，其中 msb 为不超过 n 的最大 2 的幂
    """
    # bit_length 返回二进制位数，最高位下标为 bit_length-1
    L = n.bit_length() - 1
    msb = 1 << L  # 最大的 2 的幂
    return (msb << 1) - 1 - n

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    t = int(data[0])
    idx = 1
    out_lines = []
    for _ in range(t):
        n = int(data[idx]); idx += 1
        out_lines.append(str(zeros_count(n)))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 中文注释版（ACM 风格，类名 Main）
import java.util.*;

public class Main {
    // 计算最终产生的 0 的数量
    // f(n) = 2*msb - 1 - n，其中 msb 为不超过 n 的最大 2 的幂
    static long solve(long n) {
        // 用简单循环找到 msb（不超过 n 的最大 2 的幂）
        long msb = 1L;
        while ((msb << 1) <= n) {
            msb <<= 1;
        }
        return (msb << 1) - 1 - n;
    }

    public static void main(String[] args) {
        // 数据规模不大，使用 Scanner 足够
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            long n = sc.nextLong();
            sb.append(solve(n)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// 中文注释版（ACM 风格）
#include <bits/stdc++.h>
using namespace std;

// 计算最终产生的 0 的数量
// f(n) = 2*msb - 1 - n，其中 msb 为不超过 n 的最大 2 的幂
long long solve(long long n) {
    unsigned long long msb = 1ull;
    // 通过左移找到不超过 n 的最大 2 的幂
    while ((msb << 1) <= (unsigned long long)n) {
        msb <<= 1;
    }
    unsigned long long ans = (msb << 1) - 1ull - (unsigned long long)n;
    return (long long)ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        long long n;
        cin >> n;
        cout << solve(n) << "\n";
    }
    return 0;
}

题目内容

小明手头有一个面额为 $n$ 的钞票，他试图钱生钱，魔神用语言欺骗小明将钞票给了魔神。魔神承诺拿到钞票后，会将钞票拆分成面额分别为 $n/2$，$n$ $mod$ $2$，$n/2$ 的钞票（显然钞票的总金额没有发生变化，而且会出现面值为 $0$ 的钞票），然后退回给小明。小明已经失去了理智，他会将所有面额大于 $1$ 的钞票与魔神兑换，请问他最后会有几张面额为 $0$ 的钞票。$n$ $mod$ $2$ 指 $n$ 除以 $2$ 的余数，例如 $3$ $mod$ $2 = 1，4$ $mod$ $2 = 0$ 。 $[x]$ 指最大且不大于 $x$ 的整数

输入描述

数据包括多组样例。首先输入 $T$，表示一共有 $T$ 组样例。样例最多 $100$ 组。每组输入包括一个整数 $n$ ，保证 $(1 ≤ n ≤ 10^{18})$

输出描述

对于每组数据，输出一行，包括一个正整数，表示一共有多少 $0$ 出现。

样例1

输入

1
100

输出

27

说明

$100$ 会分为 $2$ 个 $50$ 和 $1$ 个 $0$，然后分为 $4$ 个 $25$ 和 $2$ 个 $0$，然后分为 $8$ 个 $12$ 和 $4$ 个 $1$，然后分为 $16$ 个 $6$ 和 $8$ 个 $0$，然后分为 $32$ 个 $3$ 和 $16$ 个 $0$，接着分为 $64$ 个 $1$ 和 $32$ 个 $1$，至此共产生了 $27$ 个 $0$ 。