G3005 [GESP202312 三级] 小猫分鱼 题解

知识点：枚举、逆向思维、整除判断。

解题思路

设每只猫丢掉i条后拿走剩余的1/n。逆推可得初始鱼数为n^n·k-(n-1)i，最后剩鱼为(n-1)^n·k-(n-1)i。最小正剩余对应k=floor(i/(n-1)^(n-1))+1。

为什么正确

对变量S+(n-1)i，一次操作恰乘(n-1)/n；连续n次的整数条件要求初值含因子n^n，正剩余条件给出最小k。

易错点

n=1需单独处理；必须确保最后还有鱼，不能取导致剩余0的倍数；乘方用long long。

复杂度

时间O(n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n,i;
    cin>>n>>i;
    if(n==1) {
        cout<<1;
        return 0;
    }
    long long base=1,last=1;
    for(int j=0;j<n;j++)base*=n;
    for(int j=0;j<n-1;j++)last*=n-1;
    cout<<base*(i/last+1)-(n-1)*i;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。