题解：P13591 [NWRRC 2023] Kitchen Timer
loushujia
·
·
题解
前言
蒟蒻心血来潮做的一道题，因为还没有通过一道题号数字有五位数的题。
:::info[翻译（参考机翻）]
题目描述
Kenny 的厨房里有一个微波炉，配有一个奇怪的单按钮计时器界面。
当把食物放入微波炉并想开始加热时，你需要按下按钮一次或多次。第一次按下按钮时，计时器设置为 1 分钟。如果立即再次按下按钮，计时器会增加 2 分钟（总计 3 分钟）。紧接着再按一次，会增加 4 分钟，以此类推。如果连续按下按钮第 k 次，它会增加 2^{k-1} 分钟。
仅通过连续按按钮无法设置某些时间（例如 2 分钟）。幸运的是，你可以通过暂停一秒钟来重置按钮计数器。例如：按一次、暂停一秒、再按一次，可以设置 2 分钟。另一个例子：按两次（1+2）、暂停、再按三次（1+2+4），总时间为 1+2+1+2+4=10 分钟。
Kenny 需要加热食物恰好 x 分钟。请帮助他找到设置计时器所需的最少暂停次数（假设只有暂停消耗时间，按按钮的时间忽略）。
输入格式
- 第一行包含测试用例数 t（1 \le t \le 10^4)。
- 接下来 t 行，每行一个整数 x（1 \le x \le 10^{18}），表示需要加热的分钟数。
输出格式
- 对于每个测试用例，输出一个整数，表示最少暂停次数。
样例
略
说明/提示
思路
分析
As we all know， 连续按 k 次按钮，增加的分钟数为 1+2+4+…+2^{k−1}=2^k−1。所以我们可以将 x 看为 n 个 2^k-1 的和（n\ge1)。问题就转化为使 n 最小化，所求的暂停数就等于 n-1。
数学推导
蒟蒻数学不好，凑合看吧 QaQ
已知最少分段数为 n，则暂停次数为 n−1。每段对应一连续按钮序列，其和为 2^{k_i}−1 则：
x=\sum_{i=1}^n(2^{k_i}-1)=(\sum_{i=1}^n2^{k_i})-n
移项得：
x+m=\sum_{i=1}^n2^{k_i}
其中 k_i\ge1（即 2^{k_i}\ge2）。
条件：
-
- 由于每个幂次至少为 2，有 x+m\ge2m（即 x\ge m）。
-
算法
枚举即可。可以使用 GCC 内部函数快速统计 __builtin_popcountll() 一个二进制数 1 的个数。
复杂度
### 代码
```cpp
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int t;
int main()
{
scanf("%d",&t);
while (t--)
{
ll x;
scanf("%lld",&x);
// 枚举分段数 m (从 1 到 70)
for (int n = 1; n <= 70; n++)
{
if (x < n) continue; // 不满足基本条件 x ≥ m
ll num = x + n;
int cnt = __builtin_popcountll(num); // 使用内置函数计算 1 的个数
if (cnt <= n)
{
printf("%d\n",n-1); // 暂停次数 = 分段数 -1
break;
}
}
}
return 0;
}
```
[AC 记录](https://www.luogu.com.cn/record/229022372) QAQ