問題一覧 > 通常問題

No.3296 81-like number

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : くらげ / テスター : dyktr_06 Nafmo2 hanba-gu1 sepa38 おのせ
ProblemId : 12608 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-10-04 18:50:30
コンテストの他の問題:

問題文

素数 $p$ と $2$ 以上の整数 $n$ を用いて $p^n$ と表される数を 81-like number と定義します。

例えば、$81, 125, 2401$ はそれぞれ $3^4, 5^3, 7^4$ と表せるので 81-like number です。
また、$6, 11, 144$ などは素数 $p$ と $2$ 以上の整数 $n$ を用いて $p^n$ の形で表すことができないので、 81-like number ではありません。

整数 $N$ が与えられるので、$N$ 以下の 81-like number の総和を求めてください。
なお、制約の条件下で答えは $2^{63}$ 未満であることが保証されます。

制約

  • $2 \leq N \leq 10^{10}$
  • $N$ は整数

入力

$N$

出力

$N$ 以下の 81-like number の総和を $1$ 行で出力してください。

サンプル

サンプル1
入力
81
出力
315

$81$ 以下の 81-like number は $4, 8, 9, 16, 25, 27, 32, 49, 64, 81$ なので、 これらの和である $315$ を出力します。

サンプル2
入力
216
出力
858
サンプル3
入力
10000000000
出力
30756925116342

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。