题目描述 给你两个正整数n和m,你需要把n分裂成m个数相加的形式n=a1+a2+a3+.....+am，使a1 or a2 or a3 or.......or am的值最小，其中or位或运算 输入 第一行一个正整数T(1<=T<=100) 接下来的2~T+1行，每行两个正整数n和m(0<=n<1e19,1<=m<=1e19) 输出 对于每组n和m，输出一个整数，表示其按位 or 的最小值。 样例输入 5 3 1 3 2 3 3 10000 5 1244 10 样例输出 3 3 1 2000 125

题目描述

给你两个正整数$n$和$m$，你需要把$n$分裂成$m$个数相加的形式$n=a_1+a_2+a_3+...+a_m$，使$a_1$ or $a_2$ or $a_3$ or $...$ or $a_m$的值最小，其中or位或运算。

输入

第一行一个正整数$T(1 \leq T \leq 100)$。
接下来的$T$行，每行两个正整数$n$和$m$，其中$0 \leq n < 10^{19}$，$1 \leq m \leq 10^{19}$。

输出

对于每组$n$和$m$，输出一个整数，表示其按位$or$的最小值。

样例输入

5
3 1
3 2
3 3
10000 5
1244 10

样例输出

3
3
1
2000
125

算法1

Trie

(异或前缀和+Trie)

设$f(d,i,x)$表示当前匹配到第$i$位，目前状态为$x$（01串），离散化后前缀异或和与$d$的异或和最小的值。

算法流程：

- 将$n$化为$62$进制的数，然后将高位不为$1$的位置为$1$，如$778$表示为$1000000010$
- 构造$Trie$，对于每个数，二进制位按位插入。
- 二进制位按位，从高到低枚举，当前位处于$Trie$的位置为$x$，记录$XOR$当前节点位置的异或前缀和$S$,再记录当前位的$01$串$d\in \{0,1\}$。

- 如果$d=1$，即当前为$1$位。对于该位为$0$的情况，往下搜索一层，当前异或前缀和取$x$的异或前缀和。对于该位为$1$的情况，考虑当前这个$1$的位置能否改为$0$。

- 如果$x\text{ XOR }2^i>n\text{ XOR }2^i$，则它变为$0$之后它的异或前缀和更小，于是尝试让其为$0$，此时向下搜索一层，当前状态位置取相同。
- 否则不能更改，则此位必须填$1$。

- 如果$d=0$，即当前为$0$位。对于该位为$1$的情况，当前异或前缀和取$x$的异或前缀和加上$2^i$，直接向下搜索一层。对于该位为$0$的情况，也是直接向下搜索一层，当前状态位置取相同。

思考怎么证明这个算法是对的辣~

参考文献11fa456d6a68a666c819b6ebdcca99ecd2c57b3e

时间复杂度:$O(n+k^2)$，其中$k$是$n$的$62$进制长度。

C++ 代码

算法2

分块+DP

放弃阅读，ing

时间复杂度

参考文献

C++ 代码