SRM565 Div1 Medium "TheDivisionGame"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12264
訳
マナオはDivision Gameで友達と遊ぶのが好きである。
この2人用ゲームは自然数の集合 S を使って遊ぶ。
ターンは交代制で、最初のターンはマナオの番である。
各ターンにおいてプレイヤーは、 Sの中からひとつの数 X と、
X の約数である Y (ただし Y > 1 )を選択する。
それから、 S の中の X を X / Y で置き換える。
この操作で、S には同じ数字が複数含まれる可能性がでてくることに注意。
このゲームは上記の操作が出来なくなった時点で終了し、
最後に操作したプレイヤーの価値となる。
初め、S には AからBまでの自然数が1つずつ入っている。
A, Bは L <= A <= B <= Rの範囲をとりうる。
L, Rが与えられるので、お互いが最善を尽くすとして、
マナオがこのゲームに勝つA, Bのパターン数を返せ。
制約
1 <= L <= 10^9
L <= R <= L + 10^6
考えた事
素因数分解して、Sに含まれる各自然数の指数の合計値を出しておいて
例) 12 = 2^2 * 3^1 だから 2 + 1 = 3
その数を1つの山の石の数として、Nimをやるという事だよな。
ここまでは分かったんだが、xorの計算でどうしても O( 10^6 * 10^6 ) になっちまう・・
それに石の数をどうやって効率よく計算すればいいかわからん・・・
参考にしたサイト
TopCoder SRM 565 Div1 Medium TheDivisionGame - simezi_tanの日記
TopCoder SRM 565 Div1 Medium TheDivisionGame - kmjp's blog
むずいよ・・・Div1 Medium・・・
ソースコード
int a[1000050]; int t[1000050]; bool p[32000]; class TheDivisionGame { public: long long countWinningIntervals(int L, int R){ // 素数 memset( p, true, sizeof(p) ); p[0] = p[1] = false; for( int i = 2; i < 32000; i++ ){ if( !p[i] ) continue; for( int j = i + i; j < 32000; j += i ){ p[j] = false; } } // 各数値の指数の合計値を出す int n = R - L + 1; for( int i = 0; i < n; i++ ){ a[i] = L + i; } memset( t, 0, sizeof(t) ); for( int i = 2; i * i <= R; i++ ){ if( !p[i] ) continue; for( int j = (L + i - 1) / i * i; j <= R; j += i ){ while( a[j-L] % i == 0 ){ t[j-L]++; a[j-L] /= i; } } } for( int i = 0; i < n; i++ ){ if( a[i] > 1 ) t[i]++; } // xorしてく int x[50]; memset( x, 0, sizeof(x) ); for( int i = 0; i < n; i++ ){ x[t[i]]++; t[i+1] = t[i] ^ t[i+1]; } x[0]++; // パターンを出す long long res = (long long)n * (n + 1) / 2; for( int i = 0; i < 50; i++ ){ if( x[i] >= 2 ){ long long s = x[i]; res -= (s - 1) * s / 2; } } return res; } };