TopCoder SRM 565 Div1 Medium TheDivisionGame

問題

二人のプレイヤーがn個の山を使って次のようなゲームをする。

• 手番のプレイヤーは、山をひとつ選ぶ。
• この山の石の数をXとする。Xより小さいXの約数Yを選び、この山の石の数をYに変える。
• 操作のできなくなったプレイヤーの負け

最初の山のうち[A, B]の形になっているものを考える。
すなわち、A, A+1, A+2, ..., Bを最初の山とする。

L, Rが与えられたとき、L≦A≦B≦Rを満たし、ゲームにおいて両者最善を尽くしたとき先手が勝ちになるようなA, Bの組はいくつあるか求めよ。

制約条件

L, R≦10^9
R≦L + 10^6

方針

ひとつの山を見ると、操作は、Xの約数の個数を1つ以上の好きな数を減らすことであることがわかる。
すなわち、このゲームは約数の個数でnimをしていることに他ならない。

なので、[A, B]のxorが0にならないA, Bの個数を数えればよい。
これは、[A, B]のxorが0になるA, Bの個数を区間全部の個数から引くことで求める。

まずは[L, R]のそれぞれの数の約数を求める。
これは区間ふるいっぽくやればよい。

そしたら、xorでの累積和を求める。
[A, B]のxorが0のとき、[L, A - 1]のxorと[L, B]のxorが等しい。
すなわち、Aを左端とする、xorの区間の個数は、
A≦i≦Rを満たすiのうち、[L, i]のxorが[L, A - 1]のxorに等しくなるようなiの個数に等しい。

これは累積和を計算しておけば効率的に求められる。

ソースコード

int p[100000];
int a[1100000], b[1100000];
int cnt[1000];

class TheDivisionGame {
	public:
	long long countWinningIntervals(int L, int R) {
		int len = R - L + 1;
		ll ans = len * (len + 1ll) / 2;
		
		memset(cnt, 0, sizeof(cnt));
		memset(b, 0, sizeof(b));
		rep(i, len) a[i] = i + L;
		for(int i = 2; i * i < 100000; i++) if(!p[i]) for(int j = i * i; j < 100000; j += i) p[j] = 1;
		for(int i = 2; i * i <= R; i++) if(!p[i]){
			for(int j = (L + i - 1) / i * i; j <= R; j += i){
				while(a[j - L] % i == 0){
					a[j - L] /= i;
					b[j - L]++;
				}
			}
		}
		rep(i, len) if(a[i] > 1) b[i]++;
		
		int x = 0;
		rep(i, len){
			x ^= b[i];
			cnt[x]++;
		}
		x = 0;
		rep(i, len){
			ans -= cnt[x];
			x ^= b[i];
			cnt[x]--;
		}
		
		return ans;
	}
};