TopCoder SRM 845 : Div1 Hard DivNim

これは知らない知識だった。
https://community.topcoder.com/stat?c=problem_statement&pm=18002

問題

以下の変則Nimを考える。

• 普通のNimでは数を選んで引き算するが、ここでは2以上の約数で割る。
• 普通自分の手番で引き算できなくなったら負けだが、こちらが自分の手番で割り算できなくなったら勝ち。

すでに数列がある状態で、1要素だけL以上R以下の整数値を数列に加えられるとする。

• 1つめのルールだけ有効な場合、先手が勝てるのは何通りか。
• 両方のルールが有効な場合、先手が勝てるのは何通りか。

解法

引き算を除算に置き換えた場合、数列の各要素のGrundy数は、素因数分解したときの次数の総和になる。
よって、L～Rを高速に素因数分解する必要がある。愚直に1要素ずる素因数分解すると間に合わないので、うまく篩にかけて高速化しよう。

素因数分解できれば前者はあとは普通のNimと同じ。
後者は問題文中にヒントがあり、"misere"という単語がある。
misère nimで調べると、このタイプの必勝法がわかる。

• 全要素Grundy数が1の場合、偶奇で決まる。
• 1つでもGrundy数が2以上の要素がある場合、全体のxorが0か非ゼロかで決まる。

const int prime_max = 1000000;
vector<int> prime;
int NP,divp[prime_max];

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		//M[i]=NP;
		prime.push_back(i); NP++;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

int hoge(ll v) {
	int i;
	int num=0;
	FOR(i,NP) {
		int a=prime[i];
		if(1LL*a*a>v) break;
		while(v%a==0) {
			num++;
			v/=a;
		}
	}
	if(v>1) num++;
	return num;
}

class DivNim {
	public:
	vector <int> solve(long long lo, long long hi, vector<long long> board) {
		vector<ll> A;
		vector<int> num;
		for(ll v=lo;v<=hi;v++) {
			A.push_back(v);
			num.push_back(0);
		}
		int i;
		for(int a=2;a<=1000000;a++) {
			for(ll v=(lo+a-1)/a*a;v<=hi;v+=a) {
				i=v-lo;
				while(A[i]%a==0) {
					A[i]/=a;
					num[i]++;
				}
			}
		}
		
		cprime();
		vector<int> X;
		FORR(b,board) X.push_back(hoge(b));
		
		vector<int> ret(2);
		FOR(i,A.size()) {
			if(A[i]>1) num[i]++;
			int ma=num[i];
			int xo=num[i];
			FORR(a,X) {
				ma=max(ma,a);
				xo^=a;
			}
			if(xo==0) ret[0]++;
			if(ma>1) {
				if(xo==0) ret[1]++;
			}
			else {
				if(xo==1) ret[1]++;
			}
			
		}
		return ret;
	}
}

まとめ

misereという単語が問題文中になかったらダメだったな…。