むずかしかった!!!
でも、約数列挙でありがちな「 まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった!!
問題概要
整数 が与えられる。
1 以上 以下の整数のうち、 2 以上の整数
を用いて
と表せないものはいくつあるか?
制約
考えたこと
から
まで全部調べたのでは間に合わないから、なにか考えないといけない問題だね。
とりあえず が小さいと仮定して、全探索することから考えてみよう。そうしたら、
それぞれに対して
「 が
の形で表せるか」
という判定問題を解くことになる。これは次のようにして解ける。
と順にためして
と順に試して、
となったら Yes、
となったら探索終了
しかしこのままでは途方もない計算量となってしまう (ちゃんと解析すると になるはず)。
の方を動かして行く
ちょっと工夫してみよう。まず、各 に対して、
を探索していくのは無駄がある (たとえば
などを何回も見て行くことになってしまう)。
そこで、次のように発想を切り替えてみよう。
を列挙する
を列挙する
を列挙する
- ...
こうして列挙していって、その個数を から引けば良さそうだ。具体的にはどこまで探索すればよいだろうか??
それは、 までになる。なぜなら
より大きい整数は二乗すると
より大きくなるからだ。よって、次のような探索をすれば良さそう。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; } }
さて、一見これで良さそうだけど、まだ大きな罠がある。このままだと重複が発生するのだ。
という感じだ。この重複を取り除くことを考えよう!!!
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; } }
これによって、 の形で表される整数をすべて列挙できる。その個数を
から引けば OK。
注意点
重複を取り除こうとするときに、いくつか注意すべきことがある。
注意点 1:vector では MLE する
set が思いつかないと、
isab[v]
← 整数 v がの形で表せるなら True、そうでなければ False
という配列を作りたくなると思う。しかしサイズ の配列は、必要メモリ量があまりにも多いため、MLE してしまう。
注意点 2:「素数の冪乗だけ考えれば良い」は嘘
たとえば、 は
とも表せることなどから
「素数の冪乗だけ考えればよく、そうすれば重複を除去できるのではないか」
と考えた人も多かったと思う。しかしそれは嘘。
などは、素数の冪乗では表せないのだ。
コード
以上の考察をコードに落とせば OK。計算量は、Python の set を用いた場合は、
の探索範囲が
まで
- そのそれぞれについて
の探索範囲が
ということで となって十分間に合う。C++ の set を用いた場合は
となる。
#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; }