这题目本身并不难,只不过出得有 一些 “委婉”罢了。
先来研究一下题目,每次“扩充”都会将序列复制一次,然后在中间会插入一个还未使用过的最小正整数。
其实“还未使用过的 最小 正整数”,其实不过就是添加原数列中最大的值+1。
再看,扩充 $n$ 次,就会将原序列变为 $2^n-1$ 个数组成的序列(其实 $k$ 的数据范围已经提醒了),而下一次扩充,会在 $2^n$ 的位置放上一个 $n+1$。
所以第 $n$ 次扩充我们可以将它表达为:
原序列 + n + 原序列
而对于对于任意一个 $k$,它的若能整除 2,那么它就是一个“扩充得来的数”。
则我们可以得出答案:若 $k \mod 2 = 0$,则 $res+1$,否则输出答案。(初始 $res$ 为 $1$)
代码如下:
#include <bits/stdc++.h>
#define int long long//记得开 long long
using namespace std;
int n, k;
signed main()
{
scanf ("%lld%lld", &n, &k);
int res = 1;
while (!(k & 1)) k >>= 1, ++ res;//若能整除二则除,并且答案加一,否则结束。
printf ("%lld", res);
return 0;
}
想问为什么不能被二整除就直接退出循环呢
因为不能被二整除就确定了答案了。