問題一覧 > 通常問題

No.1871 divisXor

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 86
作問者 : NaHCO314NaHCO314 / テスター : MtSakaMtSaka shiomusubi496shiomusubi496
5 ProblemId : 7331 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-11 15:27:38

問題文

$f(x)$ を $x$ の正の約数の総和、 $a \oplus b$ を $a$ と $b$ のビットごとの排他的論理和と定義します。

非負整数 $N$ が与えられます。このとき、以下の条件を満たす正整数列 $A = (A_1, A_2, \ldots, A_M)$ を $1$ つ構築してください。

  • $1 \le M \le 100$
  • $f(A_1) \oplus f(A_2) \oplus \cdots \oplus f(A_M) = N$
  • $A_1 + A_2 + \cdots + A_M \lt 2 \times N$
  • $A$ は相異なる

ただし、条件を満たす $A$ が存在しない場合は $-1$ を出力してください。

入力

$N$
  • $N$ は整数
  • $0\le N\le 10^{12}$

出力

条件を満たす $A$ が存在する場合、以下の形式で出力してください。

$M$
$A_1$ $A_2$ $\cdots$ $A_M$

条件を満たす $A$ が存在しない場合、 $-1$ を一行に出力してください。

サンプル

サンプル1
入力
17
出力
3
1 6 12

$f(1) \oplus f(6) \oplus f(12) = 1 \oplus 12 \oplus 28 = 17$ です。 また、 $1 + 6 + 12 = 19 \lt 2 \times 17 = 34$ であり、条件を満たします。

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

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