kmjp's blog

競技プログラミング参加記です

Codeforces ECR #169 : E. Not a Nim Problem

ちょっと手間取った。
https://codeforces.com/contest/2004/problem/E

問題

Nimの変形問題である。
石の山から取れる石の数が、現在の石の数と互いに素でならなければならないという条件を加えたとき、石の初期状態に対する勝者を答えよ。

解法

石の数xに対するGrundy数g(x)は、実験するとこうなる。

  • g(1) = 1
  • 偶数xに対しg(x)=0
  • 奇素数xに対し、g(x)はxが何番目の素数かを示す
  • 奇数の合成数xに対し、g(x)は最小の素因数pに対するg(p)と同じ

ここまでわかれば、あらかじめg(x)をx=1~10^7まで求めておけばよい。

int T;
int N,A[303030];

int G[10202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	G[1]=1;
	int nex=2;
	for(i=3;i<=10000000;i+=2) if(G[i]==0) {
		G[i]=nex;
		for(ll j=1LL*i*i;j<=10000000;j+=i) if(j%2&&G[j]==0) G[j]=nex;
		nex++;
	}
	
	
	
	cin>>T;
	while(T--) {
		cin>>N;
		int ni=0;
		FOR(i,N) {
			cin>>A[i];
			ni^=G[A[i]];
		}
		if(ni) cout<<"Alice"<<endl;
		else cout<<"Bob"<<endl;
	}
}

まとめ

実験せずに解ける人結構いるのかな?