問題一覧 > 通常問題

No.2479 Sum of Squares

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 195
作問者 : takumaiqtakumaiq / テスター : ytqm3ytqm3 keisuke6keisuke6
1 ProblemId : 10135 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-22 17:32:27

問題文

正整数 $S$ が与えられるので、次の条件を満たす長さ $15$ 以下の正整数列 $A$ を一つ求めてください。

  • $A_i (1 \leq i \leq |A|)$ は平方数
  • $\displaystyle \sum_{i=1}^{|A|} A_i=S$

入力

$S$
  • $1 \leq S \leq 10^{18}$
  • 入力はすべて整数

出力

一行目に数列の長さを出力し、二行目に数列の要素を空白区切りで一行で出力せよ。

サンプル

サンプル1
入力
14
出力
3
1 4 9

$14=1+4+9$ で、$1,4,9$ は全て平方数です。

サンプル2
入力
43
出力
3
25 9 9

$43=25+16+1+1$ とも表せます。解は複数通りあり得ます。

サンプル3
入力
34764
出力
10
8100 4 3721 784 100 1225 8649 7056 900 4225

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