自动搬运

查看原文

来自洛谷，原作者为

	MingDynasty 最后在线时间:2025.8.23 21:03|team/76415出题组|开局一个碗,结局一根绳|坐标你猜|小升初蒟蒻,欢迎吊打|5天内2小号互关(大号paste/lb3d6tr9),可提醒,不可炸铃接龙|题解不懂私|主页article/hu9a8skr

搬运于2025-08-24 23:00:25，当前版本为作者最后更新于2025-04-12 16:14:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

题目思路：

考虑最优方式。如果 $LNC$ 取了 $y$ 个棋子，$LJJ$ 取 $k - y\bmod k$，可以让 $LNC$ 先手必赢。这也是最优的方案。换言之，如果当前的 $y$ 一次性不能被取完，那么此时的 $y$ 就是答案。由于 $3\leq x$，所以 $y$ 需要从 $2$ 开始枚举。
于是这个题变成了求最小的 $k$，使得 $k \nmid x$ 且 $k$ 最小。

时间复杂度最高 $O(T \log x)$。

需要注意 $x \le 10^{18}$。

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int ans(int x){
	for(int i=2;i<=x;i++){
		if(x%i!=0) return i;
	}
	return -1;
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int k;
	cin>>k;
	while(k--){
		int x;
		cin>>x;
		cout<<ans(x)<<'\n';
	}
	return 0;
}