洛谷 B3925：[GESP202312 三级] 小猫分鱼 → nxt=(cur-x)/n*(n-1)

​【题目来源】
https://www.luogu.com.cn/problem/B3925

【题目描述】
海滩上有一堆鱼，N 只小猫来分。第一只小猫把这堆鱼平均分为 N 份，多了 i<N 个，这只小猫把多的 i 个扔入海中，拿走了一份。第二只小猫接着把剩下的鱼平均分成 N 份，又多了 i 个，小猫同样把多的 i 个扔入海中，拿走了一份。第三、第四、……，第 N 只小猫仍是最终剩下的鱼分成 N 份，扔掉多了的 i 个，并拿走一份。
编写程序，输入小猫的数量 N 以及每次扔到海里的鱼的数量 i，输出海滩上最少的鱼数，使得每只小猫都可吃到鱼。
例如：两只小猫来分鱼 N=2，每次扔掉鱼的数量为 i=1，为了每只小猫都可吃到鱼，可令第二只小猫需要拿走 1 条鱼，则此时待分配的有 3 条鱼。第一只小猫待分配的鱼有 3×2+1=7 条。

【输入格式】
总共 2 行。第一行一个整数 N，第二行一个整数 i。
保证 0<N<10；i<N 。​​​​​​​

【输出格式】
一行一个整数，表示满足要求的海滩上最少的鱼数。​​​​​​​

【输入样例】
3
1​​​​​​​

【输出样例】
25

【数据范围】
0<N<10；
i<N 。

【算法分析】
● 核心逻辑
首先，设定如下三个假设。
（1）第 k 只猫进行分配前的鱼数为 cur；
（2）第 k 只猫进行分配后，留给第 k+1 只猫的鱼数为 nxt；
（3）小猫总个数为 n，每次扔掉的鱼数为 x。
则，第 k 只猫留给第 k+1 只猫的鱼数为：nxt=(cur-x)/n*(n-1)。由于本文代码是“逆推”（从第 n 只猫到第 1 只猫），所以等价变换可得 cur=nxt/(n-1)*n+x。

● 为什么只有 1 只猫时输出 1 ？当 n=1 时，m 只能为 0（因 m < n 且为非负整数）。所以，1 只猫需至少拿 1 条鱼，分配前鱼数 = 1×1 + 0=1，是满足规则的最小值。

【算法代码】

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

int cal(int cur,int n,int x) {
    int t=cur*n+x;
    for(int i=2; i<=n; i++) {
        if(t%(n-1)!=0) return 0;
        t=t/(n-1)*n+x;
    }
    return t;
}

int main() {
    int n,x;
    cin>>n>>x;
    /*if(n==1) {
        cout<<1<<endl;
        return 0;
    }*/
    int cur=1;
    while(true) {
        int ans=cal(cur,n,x);
        if(ans>0) {
            cout<<ans<<endl;
            break;
        }
        cur++;
    }

    return 0;
}


/*
in:
2
1

out:
7
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/129139056
https://blog.csdn.net/hnjzsyjyj/article/details/150866650



 

​