【CCF GESP 3 级】小猫分鱼 洛谷 B3925

这道题正推会 TLE #2。那怎么办，只能倒推咯。

参考了一下这位的题解，但是他写的解释太简单了，代码还用了很高级的东西！可能会让新手们一头雾水。于是我就重新讲讲。

思路：

• 每一步鱼的个数写作 $X$。

先循环一个 $k$，从一开始，一直往下循环，代表最后的 $X$ 的一份的的大小。

在每一次循环中：用一个 $ans$ 代表最终结果，最开始的时候根据题意，我们让 $ans=k\times N+i$，这就是最后一步时，$X$ 的大小。

每一次向上推理，让 $ans=ans÷(N-1)\times N+i$ 代表前一步的 $X$ 的大小。

这里可能就有小伙伴问了：为什么是这样？

• 在这里，这个前一步的 $X$ 写作 $X_1$。

我们想一想，当前这个 $X$，是不是 $(X_1-i)÷N\times (N-1)$？

我们观察到：这里的 $X$，就是 $X_i$ 减去分成 $N$ 份的多余部分之后的 $N-1$ 份？

那不就解释了这个式子了吗？既然是 $N-1$ 份，那就 $÷N-1\times N$ 再把 $i$ 加上不就完了？

还要注意：如果 $X$ 不能整除 $N-1$ 了，就要返回不能作为答案。原因也很简单：都是 $N-1$ 份了，你都不能整除 $N-1$，那肯定没办法 推下一步啊！

最后如果 $N-1$ 次（因为最后一步已经被推出来了）没有满足上文的“如果 $X$ 不能整除 $N-1$ ”，那么就是合法的方案，输出 $ans$ 即可。

讲完了，上码：

/****************************************
作者:
版权:
日期:
*****************************************/
#include<bits/stdc++.h>
#define LL k<<1
#define RR k<<1|1
#define int long long

using namespace std;
int n,i,ans;
inline bool check(int k){
	ans=k*n+i;
	for(int j=1;j<=n-1;j++){
		if(ans%(n-1)!=0)return 0;
		ans=ans/(n-1)*n+i;
	}
	return 1;
}
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>i;
	int k=1;
	while(1){
		if(check(k)){
			cout<<ans;
			exit(0);
		}
		++k;
	}
	return 0;
}