自身の2倍 [Hokkaido University Programming Contest 2019 Day 1 B]

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/B

前提知識

• エラトステネスの篩を使った区間約数列挙

解説

https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3745884

クエリ問題への取り組み方はいろいろあるが、今回は事前計算が使えそう。
ok[n] := 2≦M≦nかつ、Mが問題の条件を満たす個数
これを事前計算してあればいい。
これは、
ok[n] := M=nかつ、Mが問題の条件を満たす個数
が計算できれば、累積和をとることで構築できる。
よって、後者を高速に求めることを考える。

この配列を作るには、2≦M≦10⁵の各数を高速に約数列挙する必要があるが、
これには知られた方法がある。エラトステネスの篩である。
自分はどちらかというと、こちらから先に思いつき、このアルゴリズムを使うためにはどう考えていくかという逆の方向で考えを進めていっている。
エラトステネスの篩で各整数について高速に約数列挙した後、2M≦約数のうちMを除いたものの総積であるかを判定する。
オーバーフローを恐れて、判定しながら総積を求めていっている。

int A[101010];
vector<int> PS[101010];
int ok[101010];
int Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    rep(i, 2, 101010) A[i] = i;
    rep(p, 2, 101010) for (int x = p; x < 101010; x += p) if (A[x] % p == 0 and p < A[x]) PS[x].push_back(p);
    rep(p, 2, 101010) {
        int tot = 1;
        fore(x, PS[p]) {
            tot *= x;
            if (p * 2 <= tot) {
                ok[p] = 1;
                break;
            }
        }
    }
    rep(p, 2, 101010) ok[p] += ok[p - 1];

    cin >> Q;
    rep(q, 0, Q) {
        int n; cin >> n;
        printf("%d\n", ok[n]);
    }
}