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 → stdout
输入 stdin
CtrlShiftEnter
输出 stdout

                
错误 stderr

                
CtrlEnter提交
自动保存已开启
操作成功
wzs_oj@kernel:~ — wzs-sh
guest@wzsoj:~$
刷新页面 F5
复制 Ctrl+C
粘贴 Ctrl+V
搜索题目
站点公告
今日神谕
CSP 倒计时
排行榜
我的提交
Esc 关闭 Enter 跳转 支持模糊匹配数字