题解

题目解析

• 输入输出：输入两行，第一行为整数 $N$（小猫数量），第二行为整数 $i$（每次扔到海里的鱼数）。输出满足条件的最少初始鱼数，使得 $N$ 只小猫都能按规则分到鱼。
• 数据范围：$0 < N < 10$，$0 \le i < N$，数据规模极小，允许枚举策略。
• 复杂度要求：由于 $N \le 9$，通过枚举最终剩余鱼数并倒推验证，时间复杂度 $O(k \cdot N)$，其中 $k$ 为找到的合法解对应的枚举次数，实际运行远低于 $1\text{s}$。
• 算法知识点：逆向递推、枚举验证、模拟

思路解析

1. 逆向思维：正向求解初始鱼数困难，改为从最后一只小猫分完后剩余的鱼数倒推初始值。设第 $N$ 只小猫拿走一份后，剩余 $k(N-1)$ 条鱼（必须是 $N-1$ 的倍数，因为剩余 $N-1$ 份）。
2. 递推关系：若某只小猫分完后剩余 $ans$ 条，倒推该小猫分之前的鱼数：
   • 设分之前有 $x$ 条，扔掉 $i$ 条后剩 $x-i$，分成 $N$ 份每份 $\frac{x-i}{N}$，拿走一份后剩 $\frac{x-i}{N}(N-1) = ans$
   • 解得 $x = ans + \frac{ans}{N-1} + i$
   • 因此倒推公式为：ans = ans + ans/(N-1) + i（需保证 $ans$ 能被 $N-1$ 整除）
3. 枚举与验证：从小到大枚举正整数 $k$，令 ans = k*(N-1) 作为最终剩余鱼数，连续倒推 $N$ 次。若每次倒推时 ans % (N-1) == 0 均成立，则得到的 ans 即为最小初始鱼数。
4. 终止条件：由于 $k$ 从 $1$ 开始递增，第一个满足全部 $N$ 次整除条件的 ans 就是理论最小值。

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, r;  // n:小猫数量N, r:每次扔掉的鱼数i
    cin >> n >> r;
    
    // 枚举第N只小猫拿走后剩余的鱼数系数k
    // 实际剩余鱼数为 k * (n-1)，必须是(n-1)的整数倍
    for (int k = 1; ; k++) {
        int ans = k * (n - 1);  // 当前倒推过程中的鱼数，初始为最后剩余
        bool flag = true;       // 标记当前k是否合法
        
        // 倒推n次：从第N只小猫倒推到第1只小猫
        for (int i = 1; i <= n; i++) {
            // 关键：倒推公式要求当前ans能被(n-1)整除
            // 因为上一步的剩余 = 上一步的每份数量 * (n-1)
            if (ans % (n - 1) == 0) {
                // 倒推公式：x = ans + ans/(n-1) + r
                // 其中ans/(n-1)是上一只小猫分鱼时每份的数量
                ans += ans / (n - 1) + r;
            } else {
                flag = false;  // 出现非整数，当前k不合法
                break;
            }
        }
        
        // 若n次倒推均满足整除条件，ans即为所求最小初始鱼数
        if (flag) {
            cout << ans << endl;
            break;
        }
    }
    return 0;
}