No.3296 81-like number
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 125
作問者 :
くらげ
/ テスター :
dyktr_06
Nafmo2
hanba-gu1
sepa38
おのせ
タグ : / 解いたユーザー数 125
作問者 :


問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。