ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

キャディプログラミングコンテスト2021(ABC193) C - Unexpressed【Python解答例】

f:id:ebisuke33:20210319150303p:plain
AtCoder Beginner Contest193のC - UnexpressedについてPythonの解答例を記事にしていきます。
atcoder.jp


AtCoder Beginner Contest193 C - Unexpressed

C - Unexpressed

問題文

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

制約

・N は整数
・1≤N≤10^10

解答例

n = int(input())

Range = int((pow(n,0.5))) # 探索範囲はnの平方根まで

s = set() # 重複した値をカウントしたくないのでset型
for a in range(2,Range+1):
    tmp = a * a     # a^2から探索
    while tmp <= n: # nを超えたら終了
        s.add(tmp)  # n以下ならsetに追加
        tmp *= a    # さらにaをかけて探索

print(n - len(s))   #求める値はnからsに格納された数を引いた値

解説

問題文のように1以上N以下の整数について、a^b(a,bは2以上の整数)で表すことができない数の個数を答える問題です。

a,bは2以上の整数なのでNの平方根以上は探索する必要がなくなります。

探索していくなかでa^bが同じ値になった場合は重複して数えたら間違いになります。
重複しない値だけ集めたいのでsetを用いました。

for文でaについて、a^2から探索を始めます。
a^2がn以下ならsetに追加し、さらにaをかけます。
これを繰り返すことでsetにn以下のa^bの値が重複なしで格納することができました。

最後にnからset内の要素数をひいた値を解答してACでした。

NG例

import math

n = int(input())

Range = int((pow(n,0.5)))

res = 0
for a in range(2,Range+1):
    tmp = int(math.log(n,a)) - 1 # 対数を用いたが重複して数えてしまう
    if tmp >= 1:
        res += tmp

print(n - res)

このコードはコンテスト中に解答してNGだった例です。

正解と違うのはa^b <= nを満たすbを対数を用いて求めていったところです。
このため例えば2^4 = 4^2 = 16のように同じ値をとる組み合わせを重複して数えてしまっていました。
重複を考慮できていないのでWAが出てしまいます。



C問題は残念ながらコンテスト中に解くことができませんでした。
重複していることに気付くことができず悔しいです。
もっと冷静に考えられるよう精進したいです。


ABC193の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com