No.3254 Xor, Max and Sum
タグ : / 解いたユーザー数 60
作問者 :
Iroha_3856
/ テスター :
lif4635
champignon
tikuwa_
問題文
正整数 $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もしくは右上の雲マークをクリックしてアカウントを作成してください。