小猫分鱼 题解

题目分析

有 $N$ 只小猫分鱼，每次分鱼的过程完全相同：

• 当前鱼的总数设为 $S$；
• 将 $S$ 平均分成 $N$ 份，多出 $i$ 条（$i<N$）；
• 把多出的 $i$ 条扔进海里；
• 拿走其中的 $1$ 份，剩下的鱼为 $(N-1)$ 份。

设这只小猫拿走的鱼数为 $x$，则有：

拿走后剩下的鱼数为：

下一只小猫将在 $S'$ 条鱼的基础上重复上述过程。题目要求每一只小猫都能吃到鱼（即 $x \ge 1$），在此前提下求出海滩上最初最少有多少条鱼。

解题思路

正面直接求解比较困难，我们可以采用 逆向推导 结合 枚举 的方法。

从最后一只小猫（第 $N$ 只）开始考虑：假设它拿走的鱼数为 $k$（$k \ge 1$），那么它分鱼前面对的鱼总数是：

第 $N$ 只小猫分完后剩下的鱼数为 $(N-1) \times k$。这些鱼实际上是第 $N-1$ 只小猫分完后剩下的，因此：

由此可以得到第 $N-1$ 只小猫拿走的鱼数：

为使 $x_{N-1}$ 是整数，$S_N$ 必须能被 $N-1$ 整除。此时第 $N-1$ 只小猫分鱼前的总数：

按照相同的逻辑，我们可以一步一步向前推出前一只小猫分鱼前的总数，直到求出第 $1$ 只小猫分鱼前的总数 $S_1$。在逆向推导的过程中，每一步都需要当前鱼数能被 $N-1$ 整除，否则说明当前假设的 $k$ 不合法。

因为题目要求最小的初始鱼数，我们可以令 $k = 1, 2, 3, \dots$ 依次尝试，找到第一个满足所有整除条件的 $k$，最终求出的 $S_1$ 就是答案。

以样例 $2$ 为例（$N=3, i=1$）：

• 假设 $k=3$（最后一只猫拿走 $3$ 条），则 $S_3 = 3 \times 3 + 1 = 10$；
• $10 \div (3-1) = 5$，整除，$S_2 = 5 \times 3 + 1 = 16$；
• $16 \div 2 = 8$，整除，$S_1 = 8 \times 3 + 1 = 25$；
• 初始最少鱼数为 $25$，符合样例输出。

算法说明

算法流程：

1. 读入小猫数量 $N$ 和每次扔掉的鱼数 $i$。
2. 设最后一个小猫拿走的鱼数 $k = 1$。
3. 进入循环：
   • 初始化当前鱼数 ans = k * N + i（即 $S_N$）。
   • 进行 $N-1$ 次逆向推导：
     • 若 ans 不能被 $N-1$ 整除，说明当前 $k$ 不合法，跳出循环；
     • 否则更新 ans = ans / (N-1) * N + i。
   • 如果 $N-1$ 次推导全部成功，则 ans 即为 $S_1$，结束循环并输出；
   • 否则 k++，继续尝试下一个 $k$。

由于 $N<10$，答案的增长速度有限，暴力枚举可以很快找到结果。

时间复杂度分析

• 外层枚举 $k$，最坏情况下需要尝试的 $k$ 不会太大（近似为答案除以 $N$，增长速度约指数级，但 $N$ 很小）。
• 内层循环进行 $N-1$ 次，每次仅进行常数次运算，复杂度 $O(N)$。
• 整体时间复杂度大约为 $O(\text{答案的基数} \times N)$，在 $N<10$ 时完全可行。

代码实现

cpp
复制
1#include <cstdio>
2
3int main() {
4    long long n, i;
5    scanf("%lld%lld", &n, &i);
6
7    long long k = 1;          // 最后一只小猫拿走的鱼数
8    long long ans;
9
10    while (true) {
11        bool flag = true;
12        ans = k * n + i;      // 最后一只小猫分鱼前的总数
13        
14        // 向前逆推 N-1 步
15        for (int j = 1; j < n; ++j) {
16            if (ans % (n - 1) != 0) {
17                flag = false;      // 不能整除则当前 k 不合法
18                break;
19            }
20            ans = ans / (n - 1) * n + i;  // 计算上一只小猫的总数
21        }
22        
23        if (flag) break;       // 找到答案
24        ++k;                   // 尝试下一个 k
25    }
26
27    printf("%lld\n", ans);
28    return 0;
29}

代码说明

• 使用 long long 类型存储鱼的数量，避免数据溢出（即使 $N$ 很小，逆推过程中数值也会快速变大）。
• 变量 k 表示最后一只小猫拿走的鱼数，从 $1$ 开始枚举。
• ans 初始化为 $N \times k + i$，即最后一只小猫面前的鱼数。
• 循环 $N-1$ 次，每次判断整除并反向推出上一只小猫分鱼前的总数。
• 一旦某次不能整除，立即使 flag = false 并跳出内层循环，增加 $k$ 重试。
• 找到第一个满足所有条件的 $k$ 后，输出最终的 ans。

总结

本题的关键在于从后向前递推，将“平均分成 $N$ 份多 $i$”的过程转化为整数整除的条件。通过枚举最后一只小猫拿走的份数，并逆向验证每一步的合法性，即可高效求出海滩上最少的鱼数。该方法直观、易于实现，适合初学者练习递推与枚举的基本技巧。