N 只小猫依次分鱼,每只都把鱼均分成 N 份、扔掉多的 i 个、拿走一份,求海滩上最少的鱼数。
海滩上有一堆鱼,N 只小猫来分。第一只小猫把鱼平均分成 N 份,多了 i 个(i < N),把多的 i 个扔进海里、拿走一份。第二只小猫接着把剩下的鱼再平均分成 N 份,又多了 i 个,同样扔掉 i 个、拿走一份……第 N 只小猫也是这样操作。
输入 N 和 i,输出海滩上最少的鱼数,使得每只小猫都能吃到鱼。
例:N = 2、i = 1 时答案是 7。
逆向推导整除判定枚举最小值模拟
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N;第二行 i |
| 输出 | 满足要求的最少鱼数 |
| 数据范围 | 0 < N < 10 |
| 余数条件 | i < N |
| 样例 | N = 2, i = 1 → 7;N = 3, i = 1 → 25 |
s ÷ N × (N − 1) + i,也就是 s × (N − 1) ÷ N + i我们从最后一只猫开始往前推。设最后一只猫拿走 r 条鱼。
设某只猫待分配 s 条,它把 s 分成 N 份、扔掉 i 个
拿走 1 份后,剩 N − 1 份给后面的猫
所以上一只猫待分配 = s × N ÷ (N − 1) + i
并且 s × N 必须能被 (N − 1) 整除
这是倒推的核心公式
第三只猫待分配 = 1 × 3 + 1 = 4
往前:4 × 3 ÷ 2 + 1 = 6 + 1 = 7 ✅ 整除
再往前:7 × 3 = 21,21 ÷ 2 → 不整除 ✗
❌ r = 1 不成立
第三只猫待分配 = 2 × 3 + 1 = 7
往前:7 × 3 = 21,21 ÷ 2 → 不整除 ✗
❌ r = 2 不成立
第三只猫待分配 = 3 × 3 + 1 = 10
往前:10 × 3 ÷ 2 + 1 = 15 + 1 = 16 ✅ 整除
再往前:16 × 3 ÷ 2 + 1 = 24 + 1 = 25 ✅ 整除
✅ 全部成立,答案是 25
| 步骤 | 说明 | 数值 |
|---|---|---|
| 最后一只猫拿走 | 设为 r = 3 | 3 |
| 第三只猫待分配 | r × N + i = 3 × 3 + 1 | 10 |
| 往前推一次 | 10 × 3 ÷ 2 + 1 | 16 |
| 再往前推一次 | 16 × 3 ÷ 2 + 1 | 25 |
s × N ÷ (N − 1) + i,并且要求 s × N 能被 N − 1 整除。这一步的乘除顺序是最容易写错的地方。倒推得到 25 后,我们正着走一遍确认。
| 操作 | 待分配鱼数 | 分成 N 份 | 扔掉 i 个 | 拿走一份后剩余 |
|---|---|---|---|---|
| 第 1 只猫 | 25 | 25 ÷ 3 = 8 余 1 | 扔 1 | 24 ÷ 3 × 2 = 16 |
| 第 2 只猫 | 16 | 16 ÷ 3 = 5 余 1 | 扔 1 | 15 ÷ 3 × 2 = 10 |
| 第 3 只猫 | 10 | 10 ÷ 3 = 3 余 1 | 扔 1 | 9 ÷ 3 × 2 = 6 |
枚举最后一只猫拿走的份数 r,往前推 N−1 次,全部整除即答案
设最后一只猫拿走 x 份,尝试推出初始鱼数的解析式
N^N − (N − 1) 一类的表达式,但本题 i 可变化,公式要分情况讨论,不如枚举省事。| 方案 | 代码量 | 可靠性 |
|---|---|---|
| 倒推枚举 | 约 10 行 | ⭐⭐⭐⭐⭐ |
| 通项公式 | 约 15 行 + 推导 | ⭐⭐(易错) |
输入 N 和 i,程序会从最后一只猫开始往前推,展示每一步的数值和整除判定。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int main() { int N, i; scanf("%d %d", &N, &i); // 枚举最后一只猫拿走的份数 r(从 1 开始,保证每只猫都能吃到鱼) for (int r = 1; ; r++) { long long cur = 1LL * r * N + i; // 最后一只猫的待分配鱼数 bool ok = true; // 往前推 N-1 次,每次都要整除 for (int k = 0; k < N - 1; k++) { long long upper = cur * N; if (upper % (N - 1) != 0) { ok = false; break; } cur = upper / (N - 1) + i; } if (ok) { printf("%lld\n", cur); return 0; } } return 0; }
long long?N = 9 时答案大约是 9⁹ 量级(约 3.9 亿),虽然勉强在 int 范围内,但推过程中 cur * N 很容易瞬间超过 int 上限,务必用 long long 存中间结果。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
for (int r = 1; ; r++) | 枚举份额 | r 是最后一只猫拿走的份数,从 1 开始保证每只都有鱼吃 |
cur = 1LL * r * N + i | 最后一只猫的待分配 | 写成 1LL * 是为了强制 long long 运算 |
upper % (N - 1) != 0 | 整除判定 | 不能整除说明这个 r 不合法,换下一个 |
cur = upper / (N - 1) + i | 往前推一步 | 先乘 N 再除以 (N − 1),顺序不能反 |
cur / N * (N−1) + i,方向搞反了;② 忘了整除判定,直接用整除结果导致答案错误;③ 用 int 存中间量,cur * N 溢出。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 | 7 | 题面样例 1 |
3 | 25 | 题面样例 2 |
2 | 4 | i = 0:每次都不扔 |
3 | 23 | i = 2 的情形 |
9 | 运行验证 | 最大规模,考察 long long |
cur × N ÷ (N − 1) + i,乘和除的位置不能互换。cur × N % (N − 1) == 0 才继续。只需要几个整数变量,不需要数组。
✅ N 最大 9,枚举量极小,任何实现都瞬间完成;这题考的是逆向思维和整除判定。
// 逆向模拟的通用骨架 for (int r = 1; ; r++) { // 枚举"最后一刻"的状态 long long cur = f(r); // 由 r 推出最后一步的状态 bool ok = true; for (int k = 0; k < steps; k++) { if (!canAdvance(cur)) { ok = false; break; } // 合法性判定 cur = advance(cur); // 往前推一步 } if (ok) { /* 输出 cur */ break; } } // 整除判定与防止溢出的写法 if (cur * 1LL * N % (N - 1) != 0) { /* 不合法 */ } // 或者先除后乘(当能整除时等价) // (cur / N) 的形式要求 cur 能被 N 整除,注意条件
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 逆向推导 | 从终止状态反推初始状态 | 猴子分桃、倒水、逆序操作类题目 |
| 整除判定 | 用 % 检查可行性 | 所有"必须恰好分成整数份"的题 |
| 枚举最小解 | 从小到大试,第一个可行即最小 | 求最小解、最优解的搜索题 |