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

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

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

むずかしかった!!!
でも、約数列挙でありがちな「 \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;
}