問題一覧 > 通常問題

No.2479 Sum of Squares

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

問題文

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

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

入力

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

出力

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

サンプル

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

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

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

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

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

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