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).
单行输入包含两个整数 n 和 k(1 ≤ k ≤ n ≤ 1018)。
输出格式
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 的糖果,其异或和为 7。
在第二个样例中,例如可以选择全部六颗糖果,得到异或和 7。
输入解题思路,AI测评打分。不知道怎么写?