2315. 八戒的“大肚腩”消失计划
1000ms
256MB
简单
二分算法
题目描述
八戒制定了一个目标,一共要完成 $n$ 个仰卧起坐。
他的锻炼计划如下:
- 初始时(第 1 天到第 7 天),每天做 $m$ 个。
- 每过 7 天,他每天能做的数量就在之前的基数上增加 1 个。
- 即:第 $1 \sim 7$ 天每天做 $m$ 个,第 $8 \sim 14$ 天每天做 $m+1$ 个,第 $15 \sim 21$ 天每天做 $m+2$ 个……以此类推。
请计算八戒在第几天结束时,可以累计完成不少于 $n$ 个仰卧起坐。
输入格式
一行,包含两个正整数 $n$ 和 $m$ ($0 \lt n, m \lt 10^{18}$)。
输出格式
一个整数,表示完成任务的总天数。
样例 1
输入 (Input)
12 1
输出 (Output)
10
- 对于所有数据:$0 \lt n, m \lt 10^{18}$。
- **样例解释**:
目标 $n=12$,初始 $m=1$。
- 第 $1 \sim 7$ 天:每天 1 个,累计 7 个。
- 第 $8 \sim 10$ 天:每天 2 个,累计 $7 + 2 + 2 + 2 = 13$ 个。
- 在第 10 天结束时,累计 13 个 $\ge 12$,故输出 10。
- **算法提示**:
由于 $n$ 的范围高达 $10^{18}$,直接按天模拟循环会超时。
1. 观察规律:每 7 天为一个周期,第 $k$ 个周期($k$ 从 0 开始)每天做 $m+k$ 个,该周期总计做 $7 \times (m+k)$ 个。
2. 可以使用**二分查找**来确定总周数,或者使用等差数列求和公式直接计算。
3. **注意**:计算过程中涉及大数乘法,需防止 `long long` 溢出(C++ 中可使用 `__int128_t` 或在二分时进行溢出检查)。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功