Edit

【pythonでABC193を解説】C - Unexpressed

問題概要

問題ページ

C - Unexpressed
C - Unexpressed

問題ページへ移動する

問題文

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

制約

  • \(N\) は整数
  • \(1 ≤ N ≤ 10^{10}\)

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    d = collections.defaultdict(int)
    for i in range(2, int(n ** 0.5) + 1):
        for j in range(2, n):
            t = i ** j
            if t <= n:
                d[t]
            else:
                break
    print(n - len(d))


if __name__ == '__main__':
    solve()

-Edit
-