分数: 1000 点
问题陈述
给你正整数 N,C,K.
找到最小的正整数 X 满意 \displaystyle\min_{0\le i < N} \text{popcount}(X+Ci) \geq K.
可以证明这样一个正整数 X 始终存在。
你被给予 T 测试用例;解决它们中的每一个。
什么是popcount?
对于非负整数 x, \operatorname{popcount}(x) 是数量 1s 的二进制表示形式 x。更正式地说,对于非负整数 二进制的 x 满意 \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace),我们有 \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i.
例如, 13 是1101,所以我们有 \operatorname{popcount}(13)=3.
约束
- 1\le T \le 10^5
- 1\le N\le 10^8
- 1\le C\le 30
- 1\le K\le 30
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N C K
输出
按顺序输出测试用例的答案,以换行符分隔。
示例输入 1
3 3 1 3 6 7 12 100000000 30 30
示例输出 1
13 32711 144115183780888607
考虑第一个测试用例。
X=13 满足条件,确认如下:
- 当 i=0: \text{popcount}(X+Ci)=\text{popcount}(13)=3
- 当 i=1: \text{popcount}(X+Ci)=\text{popcount}(14)=3
- 当 i=2: \text{popcount}(X+Ci)=\text{popcount}(15)=4
没有小于的正整数 13 满足条件,所以输出 13 在第一行。