#2609. 奇偶数(慈溪2019第3题)
奇偶数(慈溪2019第3题)
Description
小W定义了一个奇偶的变换规则,当一个数x是偶数的时候,就变成x/=2,当x是奇数的时候,就变成x-1,直到x变成1。利用这个规则,我们可以写下path(x)表示从x开始按照上述规则不断变换的一个序列。例如,path(1) = [1]; path(15) = [15,14,7,6,3,2,1]; path(32) = [32,16,8,4,2,1]。
现在我们要求的是一个最大的y,使得y至少在k个path(x)里面出现,其中1≤x≤n。
例如,当n= 11; k= 3时候,答案是5,因为5在path(5); path(10); path(11)里面都出现了,具体我们看这几个:path(5) = [5,4,2,1]; path(10) = [10,5,4,2,1]; path(11) = [11,10,5,4,2,1],已经没有更大的数出现的次数至少是3次。
又比如,当n= 11; k= 6时候,答案是4,因为4在path(4); path(5); path(8); path(9); path(10);path(11)里面出现了,已经没有更大的数出现的次数至少是6次。
Input Format
number.in 输入一行仅有两个正整数n和k。Output Format
number.in 输出最大的能够满足条件的整数y。11 3
5
Hint
【输入样例 2】11 6 |
4 【输入样例 3】
|
14 5 |
6 |
1000000 100 |
31248 |
【数据范围】
对于40%的数据,1≤k≤n≤10^3。
对于80%的数据,1≤k≤n≤10^5。
对于100%的数据,1≤k≤n≤10^9。