問題一覧 > 通常問題

No.3333 Consecutive Power Sum (Large)

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 10
作問者 : wasd314 / テスター : にょぐた Vi24E
お気に入りにしたユーザー ProblemId : 12101 / 自分の提出
問題文最終更新日: 2025-11-01 08:44:53
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
wasd314 さんの単発問題コンテスト (順位表) の他の問題:

Reference

Consecutive Cubic Sum, Consecutive Power Sum (Small), and Consecutive Power Sum (Large) are, in this order, roughly each a generalization of the previous one.

Problem Statement

For three positive integers $E, L, R$, define $S(E, L, R)$ by $$ S(E, L, R) \coloneqq \sum_{i = L}^R i^E $$ .

You are given a positive integer $N$. Find all triples of positive integers $(E, L, R)$ that satisfy both of the following two conditions.

  • $1 \le L \le R$
  • $S(E, L, R) = N$

Constraints

The input $N$ is an integer between $2$ and $10^{24}$, inclusive.

Note that $N$ may not fit in 32-bit or 64-bit integer types.

Input

The input is given from standard input in the following format.

$N$

Output

We call a triple satisfying the conditions in the problem statement a solution. It can be proved that there are finitely many solutions under the constraints of this problem. If there are $C$ solutions in total and, in ascending lexicographical order, they are $$ (E_1, L_1, R_1), (E_2, L_2, R_2), \dots, (E_C, L_C, R_C) $$ then output $C + 1$ lines in the following format. Separate the values on each line with spaces, and also output a newline at the end.

$C$
$E_1\ L_1\ R_1$
$E_2\ L_2\ R_2$
$\vdots$
$E_C\ L_C\ R_C$

Since $C$ can be large, using fast input and output methods is recommended.

Sample

Sample 1
Input
2
Output
1
1 2 2

The following equation holds. Note that $L = R$ is allowed.

  • $S(1, 2, 2) = 2^1 = 2$

$(1, 2, 2)$ is the only solution.

Sample 2
Input
24979
Output
4
1 12489 12490
1 24979 24979
2 62 67
4 5 10

There may be multiple solutions.

The following equations hold.

  • $S(1, 12\,489, 12\,490) = 12\,489^1 + 12\,490^1 = 24\,979$
  • $S(1, 24\,979, 24\,979) = 24\,979^1 = 24\,979$
  • $S(2, 62, 67) = 62^2 + 63^2 + 64^2 + 65^2 + 66^2 + 67^2 = 24\,979$
  • $S(4, 5, 10) = 5^4 + 6^4 + 7^4 + 8^4 + 9^4 + 10^4 = 24\,979$

Output the solutions in ascending lexicographical order.

Sample 3
Input
987654321098765432109876
Output
4
1 41152263379115226337900 41152263379115226337923
1 123456790137345679013731 123456790137345679013738
1 329218107032921810703291 329218107032921810703293
1 987654321098765432109876 987654321098765432109876

The following equations hold.

  • $S(1, 41\,152\,263\,379\,115\,226\,337\,900, 41\,152\,263\,379\,115\,226\,337\,923) = 41\,152\,263\,379\,115\,226\,337\,900^1 + 41\,152\,263\,379\,115\,226\,337\,901^1 + 41\,152\,263\,379\,115\,226\,337\,902^1 + 41\,152\,263\,379\,115\,226\,337\,903^1 + 41\,152\,263\,379\,115\,226\,337\,904^1 + 41\,152\,263\,379\,115\,226\,337\,905^1 + 41\,152\,263\,379\,115\,226\,337\,906^1 + 41\,152\,263\,379\,115\,226\,337\,907^1 + 41\,152\,263\,379\,115\,226\,337\,908^1 + 41\,152\,263\,379\,115\,226\,337\,909^1 + 41\,152\,263\,379\,115\,226\,337\,910^1 + 41\,152\,263\,379\,115\,226\,337\,911^1 + 41\,152\,263\,379\,115\,226\,337\,912^1 + 41\,152\,263\,379\,115\,226\,337\,913^1 + 41\,152\,263\,379\,115\,226\,337\,914^1 + 41\,152\,263\,379\,115\,226\,337\,915^1 + 41\,152\,263\,379\,115\,226\,337\,916^1 + 41\,152\,263\,379\,115\,226\,337\,917^1 + 41\,152\,263\,379\,115\,226\,337\,918^1 + 41\,152\,263\,379\,115\,226\,337\,919^1 + 41\,152\,263\,379\,115\,226\,337\,920^1 + 41\,152\,263\,379\,115\,226\,337\,921^1 + 41\,152\,263\,379\,115\,226\,337\,922^1 + 41\,152\,263\,379\,115\,226\,337\,923^1 = 987\,654\,321\,098\,765\,432\,109\,876$
  • $S(1, 123\,456\,790\,137\,345\,679\,013\,731, 123\,456\,790\,137\,345\,679\,013\,738) = 123\,456\,790\,137\,345\,679\,013\,731^1 + 123\,456\,790\,137\,345\,679\,013\,732^1 + 123\,456\,790\,137\,345\,679\,013\,733^1 + 123\,456\,790\,137\,345\,679\,013\,734^1 + 123\,456\,790\,137\,345\,679\,013\,735^1 + 123\,456\,790\,137\,345\,679\,013\,736^1 + 123\,456\,790\,137\,345\,679\,013\,737^1 + 123\,456\,790\,137\,345\,679\,013\,738^1 = 987\,654\,321\,098\,765\,432\,109\,876$
  • $S(1, 329\,218\,107\,032\,921\,810\,703\,291, 329\,218\,107\,032\,921\,810\,703\,293) = 329\,218\,107\,032\,921\,810\,703\,291^1 + 329\,218\,107\,032\,921\,810\,703\,292^1 + 329\,218\,107\,032\,921\,810\,703\,293^1 = 987\,654\,321\,098\,765\,432\,109\,876$
  • $S(1, 987\,654\,321\,098\,765\,432\,109\,876, 987\,654\,321\,098\,765\,432\,109\,876) = 987\,654\,321\,098\,765\,432\,109\,876^1 = 987\,654\,321\,098\,765\,432\,109\,876$

Note that, as in this case, $N, L, R$ may not fit in 32-bit or 64-bit integer types.

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