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

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

思路:

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

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

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

每一次向上推理,让 a n s = a n s ÷ ( N − 1 ) × N + i ans=ans\div (N-1) \times N +i ans=ans÷(N1)×N+i 代表前一步的 X X X 的大小。

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

  • 在这里,这个前一步的 X X X 写作 X 1 X_1 X1

我们想一想,当前这个 X X X,是不是 ( X 1 − i ) ÷ N × ( N − 1 ) (X_1-i)\div N \times (N-1) (X1i)÷N×(N1)

我们观察到:这里的 X X X,就是 X i X_i Xi 减去分成 N N N 份的多余部分之后的 N − 1 N-1 N1 份?

那不就解释了这个式子了吗?既然是 N − 1 N-1 N1 份,那就 ÷ N − 1 × N \div N-1 \times N ÷N1×N 再把 i i i 加上不就完了?

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

最后如果 N − 1 N-1 N1 次(因为最后一步已经被推出来了)没有满足上文的“如果 X X X 不能整除 N − 1 N-1 N1 ”,那么就是合法的方案,输出 a n s ans 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;
}

Logo

集算法之大成!助力oier实现梦想!

更多推荐