問題一覧 > 通常問題

No.3296 81-like number

レベル : / AI推定難易度 : 475 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 159
作問者 : くらげ / テスター : dyktr_06 Nafmo2 hanba-gu1 sepa38 おのせ
お気に入りにしたユーザー ProblemId : 12608 / 自分の提出
問題文最終更新日: 2025-10-04 18:50:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest MMA Contest 020 (順位表) の他の問題:

Problem Statement

A number that can be expressed as $p^n$ using a prime $p$ and an integer $n$ greater than or equal to $2$ is defined as an 81-like number.

For example, $81, 125, 2401$ can be expressed as $3^4, 5^3, 7^4$ respectively, so they are 81-like numbers.
On the other hand, numbers such as $6, 11, 144$ cannot be expressed in the form $p^n$ using a prime $p$ and an integer $n$ greater than or equal to $2$, so they are not 81-like numbers.

Given an integer $N$, find the sum of all 81-like numbers less than or equal to $N$.
Under the given constraints, it is guaranteed that the answer is less than $2^{63}$.

Constraints

  • $2 \leq N \leq 10^{10}$
  • $N$ is an integer.

Input

$N$

Output

Print the sum of all 81-like numbers less than or equal to $N$ in $1$ line.

Sample

Sample 1
Input
81
Output
315

The 81-like numbers less than or equal to $81$ are $4, 8, 9, 16, 25, 27, 32, 49, 64, 81$, so print their sum, $315$.

Sample 2
Input
216
Output
858
Sample 3
Input
10000000000
Output
30756925116342

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