問題一覧 > 通常問題

No.3333 Consecutive Power Sum (Large)

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : wasd314 / テスター : にょぐた Vi24E
ProblemId : 12101 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-11-01 08:44:53
コンテストの他の問題:

参考

Consecutive Cubic Sum, Consecutive Power Sum (Small), Consecutive Power Sum (Large) はこの順におおよそ上位互換の関係にあります．

問題文

3つの正整数 $E, L, R$ に対し，$S(E, L, R)$ を $$ S(E, L, R) \coloneqq \sum_{i = L}^R i^E $$ で定めます．

正整数 $N$ が与えられます．次の2条件を共に満たす正整数の3つ組 $(E, L, R)$ を全て求めてください．

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

制約

入力される $N$ は $2$ 以上 $10^{24}$ 以下の整数です．

$N$ が 32 bit 整数型および 64 bit 整数型に収まらない場合があることに注意してください．

入力

入力は次の形式で標準入力から与えられます．

$N$

出力

問題文の条件を満たす3つ組を解と呼ぶことにします．本問題の制約下で解は有限個であることが証明できます．解が全部で $C$ 個あり，それらが辞書式順序で小さい方から順に $$ (E_1, L_1, R_1), (E_2, L_2, R_2), \dots, (E_C, L_C, R_C) $$ であるとき，次の形式で $C + 1$ 行出力してください．各行は空白区切りとし，最後に改行も出力してください．

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

$C$ が大きくなる場合があるため，高速な方法で入出力を行うことを勧めます．

サンプル

サンプル1
入力
2
出力
1
1 2 2

次の式が成り立ちます．$L = R$ でもよいことに注意してください．

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

$(1, 2, 2)$ は唯一の解です．

サンプル2
入力
24979
出力
4
1 12489 12490
1 24979 24979
2 62 67
4 5 10

解が複数あることもあります．

次の式が成り立ちます．

  • $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$

解は辞書式順序で小さい方から順に出力してください．

サンプル3
入力
987654321098765432109876
出力
4
1 41152263379115226337900 41152263379115226337923
1 123456790137345679013731 123456790137345679013738
1 329218107032921810703291 329218107032921810703293
1 987654321098765432109876 987654321098765432109876

次の式が成り立ちます．

  • $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$

このように $N, L, R$ が 32 bit 整数型にも 64 bit 整数型にも収まらない場合があることに注意してください．

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