WARush

SRMの結果とか、解けた問題のコードを書いていきます

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 の中の XX / Y で置き換える。
この操作で、S には同じ数字が複数含まれる可能性がでてくることに注意。
このゲームは上記の操作が出来なくなった時点で終了し、
最後に操作したプレイヤーの価値となる。


初め、S には AからBまでの自然数が1つずつ入っている。
A, BL <= 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 ) になっちまう・・
それに石の数をどうやって効率よく計算すればいいかわからん・・・

ソースコード

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;
    }
};