むずかしかった！！！
でも、約数列挙でありがちな「 $\sqrt{N}$ まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった！！

問題へのリンク

問題概要

整数 $N$ が与えられる。

1 以上 $N$ 以下の整数のうち、 2 以上の整数 $a,b$ を用いて $a^{b}$ と表せないものはいくつあるか？

制約

$1 \le N \le 10^{10}$

考えたこと

$1$ から $N$ まで全部調べたのでは間に合わないから、なにか考えないといけない問題だね。

とりあえず $N$ が小さいと仮定して、全探索することから考えてみよう。そうしたら、 $n = 1, 2, \dots, N$ それぞれに対して

「 $n$ が $a^{b}$ の形で表せるか」

という判定問題を解くことになる。これは次のようにして解ける。

$a = 2, 3, \dots$ と順にためして
$b = 2, 3, \dots$ と順に試して、 $a^{b} = N$ となったら Yes、 $a^{b} \gt N$ となったら探索終了

しかしこのままでは途方もない計算量となってしまう (ちゃんと解析すると $O(N^{2} \log N)$ になるはず)。

$a, b$ の方を動かして行く

ちょっと工夫してみよう。まず、各 $n = 1, 2, \dots, N$ に対して、 $a, b$ を探索していくのは無駄がある (たとえば $2^{2} = 4$ などを何回も見て行くことになってしまう)。

そこで、次のように発想を切り替えてみよう。

$2^{2}, 2^{3}, 2^{4}, \dots$ を列挙する
$3^{2}, 3^{3}, 3^{4}, \dots$ を列挙する
$4^{2}, 4^{3}, 4^{4}, \dots$ を列挙する
...

こうして列挙していって、その個数を $N$ から引けば良さそうだ。具体的にはどこまで探索すればよいだろうか？？

それは、 $\sqrt{N}$ までになる。なぜなら $\sqrt{N}$ より大きい整数は二乗すると $N$ より大きくなるからだ。よって、次のような探索をすれば良さそう。1 個目の for 文の判定条件を a * a <= N にしている。

for (long long a = 2; a * a <= N; ++a) {
    long long val = a * a;
    while (val <= N) {
        // val を列挙する

        // val に a をかける
        val *= a; 
    }
}

さて、一見これで良さそうだけど、まだ大きな罠がある。このままだと重複が発生するのだ。

$3^{4} = 81$
$9^{2} = 81$

という感じだ。この重複を取り除くことを考えよう！！！　

set を使う

重複を取り除くためには、set (C++ でも Python でもともに) を使うのが有効だ。こんなふうにする。

set<long long> ab;
for (long long a = 2; a * a <= N; ++a) {
    long long val = a * a;
    while (val <= N) {
        // val を列挙する
        ab.insert(val);

        // val に a をかける
        val *= a; 
    }
}

これによって、 $a^{b}$ の形で表される整数をすべて列挙できる。その個数を $N$ から引けば OK。

注意点

重複を取り除こうとするときに、いくつか注意すべきことがある。

注意点 1：vector では MLE する

set が思いつかないと、

isab[v] ← 整数 v が $a^{b}$ の形で表せるなら True、そうでなければ False

という配列を作りたくなると思う。しかしサイズ $N$ の配列は、必要メモリ量があまりにも多いため、MLE してしまう。

注意点 2：「素数の冪乗だけ考えれば良い」は嘘

たとえば、 $9^{2} = 81$ は $3^{4}$ とも表せることなどから

「素数の冪乗だけ考えればよく、そうすれば重複を除去できるのではないか」

と考えた人も多かったと思う。しかしそれは嘘。

$6^{2} = 36$

などは、素数の冪乗では表せないのだ。

コード

以上の考察をコードに落とせば OK。計算量は、Python の set を用いた場合は、

$a$ の探索範囲が $O(\sqrt{N})$ まで
そのそれぞれについて $b$ の探索範囲が $O(\log N)$

ということで $O(\sqrt{N} \log N)$ となって十分間に合う。C++ の set を用いた場合は $O(\sqrt{N} (\log N)^{2})$ となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    set<long long> ab;
    for (long long a = 2; a * a <= N; ++a) {
        long long val = a * a;
        while (val <= N) {
            ab.insert(val);
            val *= a;
        }
    }
    cout << N - ab.size() << endl;
}

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

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

AtCoder ABC 193 C - Unexpressed (灰色, 300 点)