시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB14312611489.764%

문제

Today, a new paper has been published in the Bulletin of Apocryphal Pioneers in Computation. According to this paper, the forgotten German number theorist Wahnfried Imaginus Jacobi (1806--1853), while still a secondary student in Potsdam, investigated the decomposition of integers into sums of cubes. Among the examples noted in the surviving fragments of his notebooks are \[ 2025 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 7^3 + 8^3 + 9^3 \] and the more curious expression \[ 3 = 1^3 + 1^3 + 1^3 = 4^3 + 4^3 + (-5)^3\,,\] which shows that a solution need not be unique. Jacobi restricted his attention to small integers and probably did not know the decomposition \[ 3 = 569\,936\,821\,221\,962\,380\,720^3 + (-569\,936\,821\,113\,563\,493\,509)^3 + (-472\,715\,493\,453\,327\,032)^3 \,,\] which was discovered only recently.1 However, Jacobi did manage to prove that a decomposition into cubes always exists for all positive integers up to $9241$, the $28$th cuban prime of the first kind. Although his work was never published, references to the method appear in a marginal annotation in an 1823 letter to his famous brother Carl Gustav Jacob.

Given a positive integer $n$, output a list of at most $10\,000$ integers between $-10\,000$ and $10\,000$ such that the sum of their cubes equals $n$.


1Booker, Andrew R.; Sutherland, Andrew V. (2021), "On a question of Mordell", Proceedings of the National Academy of Sciences, 118 (11)

입력

The input consists of:

  • One line with an integer $n$ ($1\leq n\leq 9241$), the number to decompose into cubes.

출력

Output an integer $k$ ($1 \leq k \leq 10\,000$), the number of terms in your solution, followed by $k$ integers $a_1,\ldots, a_k$ ($-10\,000\leq a_i\leq10\,000$ for each $i$), such that $a_1^3 + \dots + a_k^3 = n$.

If there are multiple valid solutions, you may output any one of them.

예제 입력 1

2025

예제 출력 1

9
1 2 3 4 5 6 7 8 9

예제 입력 2

45

예제 출력 2

3
2025 -2369 1709

예제 입력 3

15

예제 출력 3

3
-1 2 2

예제 입력 4

9241

예제 출력 4

2
-55 56

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2025 J번

  • 문제를 만든 사람: Reinier Schmiermann