题目解析
* 输入输出:输入两行,第一行为整数 NNN(小猫数量),第二行为整数 iii(每次扔到海里的鱼数)。输出满足条件的最少初始鱼数,使得 NNN 只小猫都能按规则分到鱼。
* 数据范围:0<N<100 < N < 100<N<10,0≤i<N0 \le i < N0≤i<N,数据规模极小,允许枚举策略。
* 复杂度要求:由于 N≤9N \le 9N≤9,通过枚举最终剩余鱼数并倒推验证,时间复杂度 O(k⋅N)O(k \cdot N)O(k⋅N),其中 kkk 为找到的合法解对应的枚举次数,实际运行远低于 1s1\text{s}1s。
* 算法知识点:逆向递推、枚举验证、模拟
思路解析
1. 逆向思维:正向求解初始鱼数困难,改为从最后一只小猫分完后剩余的鱼数倒推初始值。设第 NNN 只小猫拿走一份后,剩余 k(N−1)k(N-1)k(N−1) 条鱼(必须是 N−1N-1N−1 的倍数,因为剩余 N−1N-1N−1 份)。
2. 递推关系:若某只小猫分完后剩余 ansansans 条,倒推该小猫分之前的鱼数:
* 设分之前有 xxx 条,扔掉 iii 条后剩 x−ix-ix−i,分成 NNN 份每份 x−iN\frac{x-i}{N}Nx−i ,拿走一份后剩 x−iN(N−1)=ans\frac{x-i}{N}(N-1) = ansNx−i (N−1)=ans
* 解得 x=ans+ansN−1+ix = ans + \frac{ans}{N-1} + ix=ans+N−1ans +i
* 因此倒推公式为:ans = ans + ans/(N-1) + i(需保证 ansansans 能被 N−1N-1N−1 整除)
3. 枚举与验证:从小到大枚举正整数 kkk,令 ans = k*(N-1) 作为最终剩余鱼数,连续倒推 NNN 次。若每次倒推时 ans % (N-1) == 0 均成立,则得到的 ans 即为最小初始鱼数。
4. 终止条件:由于 kkk 从 111 开始递增,第一个满足全部 NNN 次整除条件的 ans 就是理论最小值。
完整代码