P10702 [SNCPC2024] 下棋
本蒟蒻的第一篇题解
定位 博弈论（nim）+进制转换
相关知识
OI WIKI
正题
读题
所有
k 进制下所有数位的乘积为自身因子的数。他称之为 LNC 数。
给出 x 枚棋子，然后 LNC 选定一个整数 k (k≥2) 。随后他们交替取走若干枚棋子，要求取走的棋子数量是 k 进制意义下的 LNC 数。LNC 先手，先取完的获胜。两个人都绝顶聪明，故都会选择最优的策略。
观察
LNC数的特性：
如果一个数在
k 进制下是 LNC 数，那么这个数的各数位（除了前导零外）不能包含其他的 0。
特别地，末尾不能为 0。
博弈策略：
如果先手时石子个数末尾为 0，则先手必败。
如果先手时石子个数末尾非 0，则先手必胜。
思路（证明）
情况1：
先手时石子个数末尾为 0假设石子个数在
k 进制下表示为
n，且
n 的末尾为 0。这意味着
n 可以表示为 n=m⋅kn=m⋅k ，其中 m 是一个整数。
先手操作：
先手拿走任意数量的石子后，石子个数 n 必然不再为k 的倍数，即 $ n≡ 0 (mod k) $ 不成立
后手操作：
后手可以拿走 n 的末尾个石子，使得 n 再次变为 k 的倍数，即 $ n≡ 0 (mod k) $ 成立
重复过程：
每次先手操作后，后手总能通过拿走末尾个石子使得石子个数再次变为 k 的倍数。这个过程会一直持续，直到石子个数变为 0。
结论：
由于先手每次操作后，后手总能使得石子个数末尾恢复为 0，最终先手会遇到没有石子可以拿的局面，因此先手必败。
情况2：
先手时石子个数末尾非 0
假设石子个数在 k 进制下表示为 n，且 n 的末尾非 0。这意味着
n≡ 0 (mod k) 不成立
先手操作：
先手可以选择拿走末尾个石子，使得石子个数 n 变为 k 的倍数，即 n≡ 0 (mod k)
后手操作：
后手在这种情况下无论如何操作，石子个数
n 都会变为非 0。
重复过程：
每次先手操作后，后手操作使得石子个数末尾非 0。
这个过程会一直持续，直到石子个数变为 0。
结论：
由于先手每次操作后，后手操作使得石子个数末尾非 0，最终后手会遇到没有石子可以拿的局面，因此先手必胜。
结论
通过上述分析，我们可以得出以下结论：
如果先手时石子个数末尾为 0，则先手必败。
如果先手时石子个数末尾非 0，则先手必胜。
实现方法
解决原问题
我们需要找到一个
k，使得 n≡ 0 (mod k)
具体步骤如下：
枚举 k：
从 2 开始枚举
k，直到找到一个
k 使得
n≡ 0 (mod k)
时间复杂度分析：
由于n 的范围是 (3≤x≤1e18 )
，我们需要确保枚举
k 的时间复杂度是可接受的。
实际上，枚举
k 的时间复杂度是
O(log n) ，因为
k 只需要枚举到
n 的因数范围内。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int k,x,T;
int tim(int x) { //博弈论函数
for (int base = 2; base <= x; base++) {
int temp = x;
if(temp%base==0)continue; //如果n≡0(modk)
else return base;
}
}
signed main(){
cin>>T;
for(int i=1;i<=T;i++){
cin>>x;
cout<<tim(x)<<endl;
}
return 0;
}