1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

AtCoder Beginner Contest 193 C問題

Posted at

AtCoderを始めましたが、ABCのA・B問題はほぼ解ける、C問題は運が良ければ解けるというレベルです。
まずはC問題を難なく解けるというの目標に、まずは過去問のC問題までをどんどんやっていってます。

自力では解けなかった問題を、解説を見て、理解した内容の整理とその結果のコードを書いていきたいと思います。

#問題

整数 N が与えられます。 1 以上 N 以下の整数のうち、 2 以上の整数 a,b を用いて $a^b$ と表せないものはいくつあるでしょうか?

#解けなかった原因
問題文を素直に説こうとすると、2〜Nまで総当たりで試して数えていくことになるが、計算量が多すぎてTLEになってしまう。

#解き方
・表せないものよりも表せるものの方が数が圧倒的に少ないので、表せるもの一覧を作り、Nから一覧の個数を引いて答えを出すようにする。
・累乗なので、Nまで試行する必要はなく、Nの平方根までで十分。
・$2^4=16$と$4^2=16$など別の組み合わせで同じ数になることを考慮する。

#ACしたコード


import math

N = int(input())
end = math.ceil(math.sqrt(N))+1

l = {}
for i in range(2,end) :
    for j in range(2,end) :
        n = i**j
        if n > N :
            break;
        l[n] = 1

print(N-len(l))
1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?