📝 题目大意

给定整数 $N$，求所有满足 $N = a \times 2^b + c$ 的非负整数三元组 $(a, b, c)$ 中，$a + b + c$ 的最小值。

💡 解题思路

1. 题目分析：$N \leq 10^{18}$，$a, b, c$ 均为非负整数。直接枚举三元组不可能，但 $b$ 的范围很小——$2^b$ 指数增长，当 $2^b > N$ 时 $a$ 只能为 $0$，此时 $a+b+c = N + b \geq N$，而 $b=0$ 时取 $(a=N, c=0)$ 已经得到 $a+b+c = N$。因此 $b$ 只需枚举 $0$ 到 $\lfloor\log_2 N\rfloor$，约 $60$ 个值，完全可以暴力。

2. 算法推导：

   • 固定 $b$ 时的最优策略：对于给定的 $b$，我们需要最小化 $a + c$（因为 $b$ 固定）。由 $N = a \times 2^b + c$ 可得 $c = N - a \times 2^b$，因此 $a + c = N - a \times (2^b - 1)$。
   • 因为 $2^b - 1 \geq 0$（$b=0$ 时等于 $0$，$b \geq 1$ 时大于 $0$），$a + c$ 关于 $a$ 单调不增——$a$ 越大，$a + c$ 越小（或不变）。
   • 同时 $c \geq 0$ 要求 $a \times 2^b \leq N$，即 $a \leq \lfloor N / 2^b \rfloor$。所以 $a$ 的最大可行值就是 $a = N / 2^b$（整除），此时 $c = N \bmod 2^b$。
   • 因此对于每个 $b$，最优三元组为 $(a = N / 2^b,\ b,\ c = N \bmod 2^b)$，对应的目标值为 $N / 2^b + b + N \bmod 2^b$。
   • 枚举所有 $b$ 使得 $2^b \leq N$，取最小值即可。代码中 mul 维护 $2^b$，b 从 $0$ 递增，每次 ans = min(ans, n / mul + b + n % mul)。

3. 边界与细节：

   • $b=0$ 的情况：$2^0 = 1$，此时 $a = N$，$c = 0$，$a+b+c = N$。这是所有解的上界。
   • $N=1$：$b=0$ 时 $a=1, c=0$，答案为 $1$。$b=1$ 时 $2^1=2 > 1$，循环退出。
   • 溢出：$N \leq 10^{18}$，答案在 long long 范围内，无需取模。初始 ans 设为 9e18（大于 $10^{18}$）足够安全。
   • 循环终止条件：while (mul <= n) 在 $2^b > N$ 时退出。此时若继续枚举，$a=0, c=N$，目标值为 $N + b \geq N$，不会优于 $b=0$ 时的答案 $N$，因此提前终止是正确的。

⏱️ 复杂度分析

• 时间复杂度：$b$ 从 $0$ 枚举到 $\lfloor\log_2 N\rfloor$，共 $O(\log N)$ 次迭代，每次 $O(1)$ 运算，总复杂度 $O(\log N)$。
• 空间复杂度：仅使用常数个变量，$O(1)$。

💻 标准代码 (C++)

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

long long n, a, b, c, ans = 9e18; // ans 初始化为极大值（9e18 > 10^18）

int main(){
    cin >> n;
    long long mul = 1; // mul = 2^b
    while (mul <= n){  // 当 2^b > N 时，a 只能为 0，不会更优
        // 固定 b 时，最优的 a = n / mul, c = n % mul
        ans = min(ans, n / mul + b + n % mul);
        b++;          // 指数加 1
        mul *= 2;     // mul = 2^{b}
    }
    cout << ans << '\n';
    return 0;
}