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

問題へのリンク

問題概要

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