SRM 565 div1 med TheDivisionGame

med にしてはかなり簡単ですね。復帰戦だったのでちょうど良いけど。

問題

TopCoder Statistics - Problem Statement

U さんと K さんがゲームをする。ゲームは S = {L, L+1, ..., R-1, R} という数の集合を使って行う。そして,

• 集合 S の中から何らかの数 X を取り出す。
• X を割り切る数 Y を選ぶ(Y は 2 以上の整数)。
• X を X/Y にして集合 S に戻す。

この一連の操作ができないほうが負けである。ある二つの自然数 A, B が与えられて, L, R は A <= L <= R <= B の範囲で動く。この中で先攻の U さんが勝つ [L, R] の組み合わせは何通りあるか。

解法

明らかに grundy 数っぽいですが, この grundy 数は素因数分解の指数の和になります。

この grundy 数の xor の和が 0 になるところが負けですが, これは累積和を使えば高速に計算できます。

const int MAX = 1000100;
int value[MAX];
int cnt[MAX];
int xorCnt[555];

class TheDivisionGame {
public:
    long long countWinningIntervals(int L, int R) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = L; i <= R; i++)
            value[i-L] = i;
        for (int i = 2; i*i <= R; i++) {
            int l = L/i*i;
            if (l < L) l += i;
            for (int j = l; j <= R; j+= i) {
                while (value[j-L] % i == 0) {
                    cnt[j-L]++;
                    value[j-L] /= i;
                }
            }
        }
        for (int i = L; i <= R; i++) {
            if (value[i-L] > 1) cnt[i-L]++;
        }
        ll minus = 0;
        int now = 0;
        memset(xorCnt, 0, sizeof(xorCnt));
        xorCnt[0] = 1;
        for (int i = L; i <= R; i++) {
            now ^= cnt[i-L];
            minus += xorCnt[now];
            xorCnt[now]++;
        }
        ll d = R-L+1;
        return d*(d+1)/2 - minus;
    }
};