けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

みんなのプロコン 2018 決勝 A - Uncommon (包除原理)(600 点)

包除原理練習第二弾なん!
 a_i \le 10^{5} という制約の意味に気がつくのにかなり時間がかかったん。これのおかげで「 a_{1}, a_2, \dots, a_N の中に  v の倍数が何個あるか」というのが、 O(N) ではなく  O(\max(a) / v) でできるのんな。

Uncommon へのリンク

問題概要

 N 個の相異なる整数  a_{1}, a_2, \dots, a_N と、整数  M が与えられる。各  i = 1, 2, \dots, M に対して、

  •  a_{1}, a_2, \dots, a_N のうち  i と互いに素なものが何個あるか

を求めて出力せよ。

制約

  •  1 \le N, M, a_{i} \le 10^{5}

考えたこと

いかにも包除っぽいん。

 i = p_{1}^{e_{1}} \dots p_{K}^{e_{K}}

としてあげて、とりあえず  e_{i} が 1 より大きいやつは、1 にしたやつと答えは一緒になるので、

 i = p_{1} \dots p_{K}

と表せるものだけ考えればよい。包除原理やると、  O(2^{K}) 回の

  •  a_{1}, a_2, \dots, a_N の中に  v の倍数が何個あるか

を求める作業を行って足し引きをすればよい。 K の値は最大でも 6 (2 × 3 × 5 × 7 × 11 × 13 = 30030) なので、 2^{K} の方はほぼ定数と思えるのだが、、、

問題はこの何個あるかを求める作業が愚直にやると 1 回 1 回に  O(N) かかってしまう。自分は最初

  • この作業をやるべき  v は、素因数分解したときの指数部が 1 のものだけやればいいから、それでギリギリ間に合うのではないか

と考えて提出したけど TLE した。制約をよくみると  a_i \le 10^{5} とあってこれを活かすと、 a_{1}, a_2, \dots, a_N の中に  v の倍数が何個あるかを  O(A / v) ( A = max(a))で求めることができる。ここで

  •  1 + 1/2 + 1/2 + \dots + 1/n = O(\log{n})

であることを思い出すと、全部の  v \le A について実施しても  O(A \log{A}) で実施できる。全体として  O(A \log{A} + M2^{K} + M\sqrt{M}) で実施できて間に合う。

なお、 M素因数分解する部分については、通称 osa_k 法と呼ばれている方法によって、 O(M\sqrt{M}) から  O(M \log\log{M}) に高速化できたりする。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX = 110000;
int N, M;
bool isina[MAX];
int memo[MAX]; // memo[i] := a の中に i で割り切れるものが何個あるか
int num(int v) {
  if (memo[v] != -1) return memo[v];
  int res = 0;
  for (int i = v; i < MAX; i += v) if (isina[i]) ++res;
  return memo[v] = res;
}

int main() {
  cin >> N >> M;
  memset(isina, 0, sizeof(isina));
  memset(memo, -1, sizeof(memo));
  for (int i = 0; i < N; ++i) {
    int a; cin >> a; isina[a] = true;
  }

  vector<int> res(M+1, 0);
  res[1] = N;
  for (int k = 2; k <= M; ++k) {
    vector<int> primes;
    int tk = k;
    for (int p = 2; p*p <= tk; ++p) {
      if (tk % p != 0) continue;
      primes.push_back(p);
      while (tk % p == 0) tk /= p;
    }
    if (tk > 1) primes.push_back(tk);
    int all = 1;
    for (auto p : primes) all *= p;
    if (all < k) res[k] = res[all];
    else {
      for (int bit = 0; bit < (1<<(int)primes.size()); ++bit) {
        int con = 0, val = 1;
        for (int i = 0; i < primes.size(); ++i) if (bit & (1<<i)) ++con, val *= primes[i];
        if (con & 1) res[k] -= num(val);
        else res[k] += num(val);
      }
    }
  }
  for (int k = 1; k <= M; ++k) cout << res[k] << endl;
}