GESP 题解库 / 3 级题解 / [GESP202312 三级] 小猫分鱼 · 第 19 / 28 题
GESP202312 三级 · B3925 · 简单

小猫分鱼

N 只小猫依次分鱼,每只都把鱼均分成 N 份、扔掉多的 i 个、拿走一份,求海滩上最少的鱼数。

📊
N < 10
小猫数量
🔢
int
数值类型
⚡
O(N × 枚举)
时间复杂度
🎯
倒推 + 整除判定
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

海滩上有一堆鱼,N 只小猫来分。第一只小猫把鱼平均分成 N 份,多了 i 个(i < N),把多的 i 个扔进海里、拿走一份。第二只小猫接着把剩下的鱼再平均分成 N 份,又多了 i 个,同样扔掉 i 个、拿走一份……第 N 只小猫也是这样操作。

输入 N 和 i,输出海滩上最少的鱼数,使得每只小猫都能吃到鱼。

例:N = 2、i = 1 时答案是 7。

💡
人话翻译:每次操作都是"设当前有 s 条鱼,那么 s = N × 某整数 + i,扔掉 i 条,拿走 N 分之一"。要从最后一只猫倒着往前推,而且每一步都必须整除。

🔍 关键词提取

逆向推导整除判定枚举最小值模拟

已知条件

项目说明
输入第一行 N;第二行 i
输出满足要求的最少鱼数
数据范围0 < N < 10
余数条件i < N
样例N = 2, i = 1 → 7;N = 3, i = 1 → 25

需要解决的问题

02
思维导图
整理解题思路的全貌
🐱 从最后一只猫倒着推
📥 读入
N 只猫(< 10)
每次扔 i 个(i < N)
N、i 都是小整数
注意 i 可能是 0
🔄 倒推模型
最后一只猫拿走 r 条
它待分配 = r × N + i
往前:x × (N−1) ÷ N + i
每步都必须整除
🔍 枚举最小
r 从 1 开始试
第一个全部整除的 r 即答案
整除判定用 % N
不需要数学公式
⚠️ 易错点
正着推无从下手
整除判定漏掉
N = 1 的边界
i = 0 的情况
03
样例手算推导
样例 N = 3、i = 1 的倒推过程

🧮 样例:N = 3、i = 1,答案 25

我们从最后一只猫开始往前推。设最后一只猫拿走 r 条鱼。

1
先明确推进公式

设某只猫待分配 s 条,它把 s 分成 N 份、扔掉 i 个

拿走 1 份后,剩 N − 1 份给后面的猫

所以上一只猫待分配 = s × N ÷ (N − 1) + i

并且 s × N 必须能被 (N − 1) 整除

这是倒推的核心公式

2
尝试 r = 1

第三只猫待分配 = 1 × 3 + 1 = 4

往前:4 × 3 ÷ 2 + 1 = 6 + 1 = 7 ✅ 整除

再往前:7 × 3 = 21,21 ÷ 2 → 不整除 ✗

❌ r = 1 不成立

3
尝试 r = 2

第三只猫待分配 = 2 × 3 + 1 = 7

往前:7 × 3 = 21,21 ÷ 2 → 不整除 ✗

❌ r = 2 不成立

4
尝试 r = 3

第三只猫待分配 = 3 × 3 + 1 = 10

往前:10 × 3 ÷ 2 + 1 = 15 + 1 = 16 ✅ 整除

再往前:16 × 3 ÷ 2 + 1 = 24 + 1 = 25 ✅ 整除

✅ 全部成立,答案是 25

步骤说明数值
最后一只猫拿走设为 r = 33
第三只猫待分配r × N + i = 3 × 3 + 110
往前推一次10 × 3 ÷ 2 + 116
再往前推一次16 × 3 ÷ 2 + 125
🔑
推进方向要分清:从"第 k 只猫待分配 s"推"第 k−1 只猫待分配",要先把 s 乘回 N 份再除以 (N−1) 份,即 s × N ÷ (N − 1) + i,并且要求 s × N 能被 N − 1 整除。这一步的乘除顺序是最容易写错的地方。

🧮 正向验证:25 条鱼确实是可行的

倒推得到 25 后,我们正着走一遍确认。

操作待分配鱼数分成 N 份扔掉 i 个拿走一份后剩余
第 1 只猫2525 ÷ 3 = 8 余 1扔 124 ÷ 3 × 2 = 16
第 2 只猫1616 ÷ 3 = 5 余 1扔 115 ÷ 3 × 2 = 10
第 3 只猫1010 ÷ 3 = 3 余 1扔 19 ÷ 3 × 2 = 6
💡
注意最后剩余的 6 条:题目只要求每只猫都分到鱼并拿走一份,没有要求最后剩余为 0。这一点容易误解,很多同学会强行让剩余为 0 导致算不出来。
04
解法对比
倒推枚举 vs 数学公式

⚔️ 解法对比

🟢 倒推 + 枚举份额(推荐) 推荐

枚举最后一只猫拿走的份数 r,往前推 N−1 次,全部整除即答案

  • N < 10,枚举量极小
  • 逻辑与题面一一对应
  • 不需要推导通项公式
  • 代码 10 行
💡
为什么够用:N 最大 9,而最小解的份额 r 通常不大,枚举几十次就能命中,完全不用担心效率。

🟠 推通项公式

设最后一只猫拿走 x 份,尝试推出初始鱼数的解析式

  • 经典"猴子分桃"型问题
  • 公式含 (N−1)^N 的幂
  • 需要配合整除条件求解
  • 推导复杂易错
⚠️
结论:这类问题的通用形式是 N^N − (N − 1) 一类的表达式,但本题 i 可变化,公式要分情况讨论,不如枚举省事。

📈 性能对比

方案代码量可靠性
倒推枚举约 10 行 ⭐⭐⭐⭐⭐
通项公式约 15 行 + 推导⭐⭐(易错)
05
算法流程图
枚举份额,往前推 N−1 次
开始读入 N、ir 从 1 开始枚举(最后一只猫拿走的份数)cur = r × N + i往前推 N−1 次,每步 cur × N 都能被 (N−1) 整除吗?是 ✓输出 cur 并结束否 ✗r 加 1 重新试结束r 加 1 继续试
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🐱 小猫分鱼倒推器

输入 N 和 i,程序会从最后一只猫开始往前推,展示每一步的数值和整除判定。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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 溢出。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
2
1
7题面样例 1
3
1
25题面样例 2
2
0
4i = 0:每次都不扔
3
2
23i = 2 的情形
9
8
运行验证最大规模,考察 long long
✅
自查清单:① 是从最后一只猫倒推吗?② 每步都做了整除判定吗?③ 用 long long 了吗?

🚨 易错点清单

⚠️
推进方向写反:必须是 cur × N ÷ (N − 1) + i,乘和除的位置不能互换。
⚠️
漏掉整除判定:不检查整除就会算出错误的"伪解",必须 cur × N % (N − 1) == 0 才继续。
⚠️
用 int 存中间量溢出:N = 9 时中间值可达 10⁹ 量级,乘以 N 后必然溢出。
⚠️
以为最后必须剩 0 条:题目只要求每只猫都分到鱼,剩余不为 0 也是允许的。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(枚举 × N)
空间复杂度
O(1)
N 最大
9
枚举次数
通常几十次

时间怎么算的?

空间都用在哪?

只需要几个整数变量,不需要数组。

✅ N 最大 9,枚举量极小,任何实现都瞬间完成;这题考的是逆向思维和整除判定。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 逆向模拟的通用骨架
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 整除,注意条件

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
逆向推导从终止状态反推初始状态猴子分桃、倒水、逆序操作类题目
整除判定用 % 检查可行性所有"必须恰好分成整数份"的题
枚举最小解从小到大试,第一个可行即最小求最小解、最优解的搜索题
🌟
思考题:如果题目改成"求最大的鱼数(在某个上限以内)",枚举方向该怎么调整?(提示:把所有可行的 r 都找出来、取对应的最大 cur,但要注意题目是否有上界约束——没有上界时"最大的鱼数"是无穷大。)