CF912B.New Year's Eve

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Since Grisha behaved well last year, at New Year's Eve he was visited by Ded Moroz who brought an enormous bag of gifts with him! The bag contains n sweet candies from the good ol' bakery, each labeled from 1 to n corresponding to its tastiness. No two candies have the same tastiness.

The choice of candies has a direct effect on Grisha's happiness. One can assume that he should take the tastiest ones — but no, the holiday magic turns things upside down. It is the xor-sum of tastinesses that matters, not the ordinary sum!

A xor-sum of a sequence of integers _a_1, _a_2, ..., a__m is defined as the bitwise XOR of all its elements: , here denotes the bitwise XOR operation; more about bitwise XOR can be found here.

Ded Moroz warned Grisha he has more houses to visit, so Grisha can take no more than k candies from the bag. Help Grisha determine the largest xor-sum (largest xor-sum means maximum happiness!) he can obtain.

由于格里沙去年表现良好,新年除夕夜,圣诞老人(Дед Мороз)前来拜访,并带来了一个装满礼物的巨大袋子!袋中装有 $ n $ 颗来自古老而优秀的面包房的甜味糖果,每颗糖果按其美味程度从 $ 1 $ 到 $ n $ 编号。任意两颗糖果的美味程度均不相同。

所选糖果的组合会直接影响格里沙的幸福感。人们或许会认为他应挑选最美味的那些糖果——但事实并非如此,节日魔法将一切颠倒过来:真正起决定作用的是美味程度的异或和(xor-sum),而非普通的算术和!

序列 $ a_1, a_2, \dots, a_m $ 的异或和定义为其中所有元素的按位异或(bitwise XOR):
,其中 表示按位异或运算;关于按位异或的更多内容,请参见此处。

圣诞老人警告格里沙,他还要去其他人家拜访,因此格里沙最多只能从袋中取走 $ k $ 颗糖果。请帮助格里沙确定他所能获得的最大异或和(最大异或和意味着最大的幸福感!)。

输入格式

The sole string contains two integers n and k (1 ≤ k ≤ n ≤ 1018).

单行输入包含两个整数 nn 和 kk(1 ≤ k ≤ n ≤ 10181 \le k \le n \le 10^{18})。

输出格式

Output one number — the largest possible xor-sum.

输出一个数字——最大的可能异或和。

输入输出样例

  • 输入#1

    4 3

    输出#1

    7
  • 输入#2

    6 6

    输出#2

    7

说明/提示

In the first sample case, one optimal answer is 1, 2 and 4, giving the xor-sum of 7.

In the second sample case, one can, for example, take all six candies and obtain the xor-sum of 7.

在第一个样例中,一个最优解是选择编号为 1、2 和 4 的糖果,其异或和为 77。

在第二个样例中,例如可以选择全部六颗糖果,得到异或和 77。

输入解题思路,AI测评打分。不知道怎么写?

首页