問題一覧 > 通常問題

No.3254 Xor, Max and Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : Iroha_3856 / テスター : lif4635 champignon tikuwa_
ProblemId : 12659 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-09-05 04:13:46

問題文

正整数 $N, M$ が与えられます。

以下の条件をすべて満たす数列 $A = (A_1, A_2, \ldots, A_N)$ について、その総和 $\displaystyle \sum_{k = 1}^N A_k$ としてありえる最大値を求めてください。

  • $0 \leq A_i \leq M\ (1 \leq i \leq N)$
  • $A_1 \oplus A_2 \oplus \ldots \oplus A_N = 0$

ただし、$\oplus$ でビットごとの排他的論理和を表します。

入力

$N\ M$

入力は全て以下の制約を満たす。

  • $1 \leq N, M \leq 10^9$
  • $N, M$ は整数

出力

答えを出力し、最後に改行してください。

サンプル

サンプル1
入力
6 6
出力
36

$A = (6, 6, 6, 6, 6, 6)$ のときに条件を満たした上で総和が $36$ となります。

総和を $37$ 以上にすることはできないので、最大値は $36$ です。

サンプル2
入力
3 7
出力
14

$A = (7, 7, 0)$ などのときに条件を満たした上で総和が $14$ となります。

総和を $15$ 以上にすることはできないので、最大値は $14$ です。

サンプル3
入力
5 100
出力
454

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