题解 ARC155D Avoid Coprime Game

题意

给定一个可重集 \(S\) ，保证 \(\gcd_{x\in S}(x)=1\) ，维护一个初始为 \(0\) 的整数 \(G\) ，双方轮流操作，每次每人选择 \(S\) 中一个数 \(x\) 满足 \(\gcd(x,G)\ne 1\) ，然后 \(G\gets \gcd(x,G)\) 同时将 \(x\) 从 \(S\) 中删去，谁无法操作谁败。

对于所有 \(x\in S\) ，询问若先手一开始选择 \(x\) 则谁会获胜。

值域 \(2\times 10^5\) ，集合大小 \(2\times 10^5\) 。

题解

分析

考虑一个局面 \((G',S')\) ，如果这个局面可以到达，那么显然 \(S\) 中所有不被 \(G'\) 整除的数 \(x\) 都必须在 \(S'\) 中，考虑哪些被 \(G'\) 整除的数 \(y\) ，如果之后的某次操作选择了 \(y\) ，那么 \(G'\) 显然不会变，所以实际上这些数对局面的影响本质是等效的，如果有 \(k\) 个这样的数，将这 \(k\) 个数从 \(S'\) 中删去得到 \(S''\) ，用局面 \((G',S'',k)\) 表示，那么后面的每次决策要么就是同时改变 \(G',S''\) ，要么就是 \(k\gets k-1\) ，所以本质上就是这两个游戏的组合，而 \(k\) 每次减一这个游戏的 SG 函数值显然就是 \(k\) 的奇偶性，所以可以得到 \(SG(G',S')=SG(G',S'')\oplus(k\&1)\) ，而值得注意的是， \(S''\) 仅由 \(G'\) 唯一确定（ \(S''\) 就是 \(S\) 中所有不能被 \(G'\) 整除的数），不妨记 \(S''=F(G')\) 。

于是你可以把所有可到达局面简化成 \((G',F(G'))\) ，而 \(G'\) 就是值域范围，所以局面就被简化为可接受的数量了，接下来就是求所有的 \(SG(G',F(G'))\) 了，局面连边数是 \(A\log A\) 级别的，暴力连边即可，这个就是看 \(F(G')\) 与 \(G'\) 的 \(\gcd\) 可能为哪些了，用莫反很好处理。（感觉没有啥更简单的方法了。。。）

总复杂度 \(O(A\log^2 A)\) 。

参考代码

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=200005;
int A[maxn],CNT[maxn],sg[maxn];
int vis[maxn],mu[maxn],pri[maxn],cnt;
int sb[maxn];
std::vector<int>fk[maxn],kf[maxn];
int main(){
	int N;scanf("%d",&N);
	for(int i=1;i<=N;++i)
		scanf("%d",&A[i]),++CNT[A[i]];
	vis[1]=true;mu[1]=1;
	for(int i=2;i<maxn;++i){
		if(!vis[i])mu[pri[++cnt]=i]=-1;
		for(int j=1;j<=cnt;++j){
			int k=i*pri[j];
			if(k>=maxn)break;
			vis[k]=true;
			if(i%pri[j]==0)break;
			mu[k]=mu[i]*mu[pri[j]];
		}
	}
	for(int i=1;i<=cnt;++i){
		for(int j=(maxn-1)/pri[i];j>=1;--j){
			CNT[j]+=CNT[j*pri[i]];
		}
	}
	for(int i=1;i<maxn;++i)
		for(int j=i;j<maxn;j+=i)
			fk[j].push_back(i);
	for(int i=1;i<maxn;++i){
		for(auto j:fk[i])if(j>1&&j<i){
			int az=0;
			for(auto k:fk[i/j]){
				az+=mu[k]*CNT[j*k];
			}
			if(az)kf[i].push_back(j);
		}
	}
	for(int i=2;i<maxn;++i){
		for(auto j:kf[i]){
			int o=sg[j];
			o^=(CNT[j]-CNT[i]-1)&1;
			sb[o]=true;
		}
		while(sb[sg[i]])++sg[i];
		for(auto j:fk[i]){
			int o=sg[j];
			o^=(CNT[j]-CNT[i]-1)&1;
			sb[o]=false;
		}
	}
	for(int i=1;i<=N;++i){
		int o=sg[A[i]];
		o^=((CNT[A[i]]-1)&1);
		puts(o?"Aoki":"Takahashi");
	}
	return 0;
}