SRM565 Div1 Medium

500

約数でニムをやる。

しかし、ニムに関してより約数を求めるところでつまずく。
区間篩なるモノがあるそうなので、それを模倣してある区間の約数を計算した。ありがとうスパソ。

class TheDivisionGame {
public:
  long long countWinningIntervals(int L, int R)
  {
    const int B = R - L + 1;
    const int N = 100000;
    static bool prime[N];
    fill(prime, prime + N, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i * i < N; ++i) {
      if (!prime[i]) continue;
      for (int j = i * i; i * j < N; j += i) {
        prime[j] = false;
      }
    }

    static lli p[N], size = 0;
    for (int i = 0; i < N; ++i) {
      if (prime[i]) p[size++] = i;
    }

    const int M = 1000000 + 10;

    static int f[M];
    fill(f, f + M, 0);

    static int num[M];
    for (int i = 0; i < M; ++i) {
      num[i] = i + L;
    }

    for (int i = 0; i < size; ++i) {
      unless (p[i] * p[i] <= R) break;
      int j;
      if (p[i] >= L) j = p[i] * p[i];
      else if (L % p[i] == 0) j = L;
      else                    j = L - (L % p[i]) + p[i];
      for (; j <= R; j += p[i]) {
        while (num[j - L] % p[i] == 0) {
          num[j - L] /= p[i];
          ++f[j - L];
        }
      }
    }
    for (int i = 0; i < M; ++i) {
      if (num[i] != 1) ++f[i];
    }

    const int F = 100;
    static int cnt[F];
    fill(cnt, cnt + F, 0);

    int nim = 0;
    for (int i = 0; i < B; ++i) {
      nim ^= f[i];
      ++cnt[nim];
    }

    lli ret = (lli)B * (lli)(B + 1) / 2;
    ret -= cnt[0];
    for (int i = 0; i < F; ++i) {
      ret -= cnt[i] * (cnt[i] - 1) / 2;
    }
    return ret;
  }
};