TopCoder SRM 565 Div1 Medium TheDivisionGame

さてMedium。500ptとはいえ割と正解者が多い回。
自分もあと一歩というとこまで行ったのにバグが取きれなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=12264

[A,B]の範囲の数列があった場合、２人が数列のうち１より大きい数値を１つ選んで約数にする。
最後に全数値を１にした方が勝ち。
[L,R]が与えられたとき、[L,R]に含まれる[A,B]のうち先手必勝なケース数を答える。

この問題は次の３手順で対応する。

1. [L,R]の素因数の合計をカウントする。
2. 素因数の数が、その数に対し最大で約数を取れる回数をGrundy数とみなす。
3. Gundy数のxorが0以外となるような[A,B]を数え上げる。

本番、２まではすんなり行って３でちょっと止まった。
R-Lが最大1000000なので、O((R-L)^2)で数えるのは無理だし。
ただ、思いついたのが[L-1,N]までのGrundry数のxorを取っておけば、[A,B]のGrundy数のxorは[L-1,A-1]^[L-1,B]で取れることに気づく。

[L,R]から[A,B]を選ぶ取り方は合計で(R-L+1)*(R-L+2)/2。
[L-1,N]をN=[L,R]で計算しておき、それぞれの値が同じになる組み合わせの分、上の合計から引いていけばよい。

int np;
ll prime[100000];
const int prime_max = 1000001;
void cprime() {
	int i,j;
	char p[prime_max];
	
	np=0;
	ZERO(p);
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[np++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=1;
	}
}
int nd[1000001];
int num[1000001];

class TheDivisionGame {
	public:
	long long countWinningIntervals(int L, int R) {
		int i,j,k,N;
		
		cprime();
		ZERO(nd);
		N=R-L+1;
		FOR(i,N) num[i]=i+L;
		FOR(i,np) {
			int p=prime[i];
			for(j=(L-1)/p*p+p;j<=R;j+=p) {
				while(num[j-L]%p==0){ num[j-L]/=p; nd[j-L]++;}
			}
		}
		
		FOR(i,N) if(num[i]>1) nd[i]++;
		ll hoge[130];
		ZERO(hoge);
		hoge[0]++;
		
		int cxor=0;
		ll res = (N+1)*((ll)N)/2;
		FOR(i,N) {
			cxor ^= nd[i];
			res -= hoge[cxor];
			hoge[cxor]++;
		}
		return (long long)res;
	}
};

まとめ

本番は、素因数分解、nim、数え上げとすぐに回答手順が思いついたのだが、肝心の素因数分解にバグがあった…。
素因数が100万以上を含む場合がうまくカウントできてなかった。

もったいないが、nimと数え上げがパッと思いついたのでいいとしておくか…。