题解 | 消减整数

一、关键观察

设第 i 步减去的数为 ai​。规则要求a1​=1,ai+1​∈{ai​,2ai​}(i≥1)因此每个 ai​ 必然是 2 的幂，且指数序列非递减，且每一步的指数最多只能 +1。

设出现的最高幂为 2k，则在序列中必有2^0,2^1,…,2^k每种至少出现一次。记 2i 出现的次数为 ci​(ci​≥1)。

于是H=∑i=0~k​{ci​2^i},L=∑i=0~k​{c^i}​.

给定正整数 H，最少需要L=⌊log2​(H+1)⌋+popcount(H+1)−1​次操作，即可恰好把 H 减到 0。

等价地，设 s=H+1，记 bitlen(s) 为二进制位数，popc(s) 为二进制中 1 的个数，则L=bitlen(s)+popc(s)−2.

二、构造方法（实际得到这么多次操作）

1. 设 t=⌊log2​(H+1)⌋，r=H+1−2t。
2. 对 i=0,1,…,t−1 依次执行减去 2i（必定要做的一次），若 r 的第 i 位为 1，再减去一次同样的 2i（这一次是“额外”的）。这样得到的序列长度为 t+popcount(r)，恰好等于上面公式给出的最小次数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll H;
    cin >> H;

    ll s = H + 1;
    int bitlen = 64 - __builtin_clzll(s);
    int popc   = __builtin_popcountll(s);
    ll ans = (ll)bitlen + popc - 2;

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}