CF2242E Product of Closures

设正整数 $x > 0$ 的“闭包”为如下的无限二进制字符串 $C(x)$： 1. 将 $x$ 用二进制形式表示，不含前导零； 2. 将所得字符串无限次自我拼接，记作 $C(x)$。 例如，$C(1) = 11111…$，$C(4) = 10010010010010…$，$C(9) = 100110011001…$。 记两个闭包的积 $C(x) \mathop{\&} C(y)$ 为对应位按位且得到的无限二进制串。例如，对 $C(4) \mathop{\&} C(9)$，有： $$ \begin{array}{r} \begin{array}{r} C(4)\\ C(9)\\ \end{array} \mathop{\&} \begin{array}{r} 100100100100100100...\\ 100110011001100110...\\ \end{array} \\ \hline \begin{array}{r} 100100000000100100... \end{array} \end{array} $$ 给定整数 $l$, $r$, $n$。在区间 $[l, r]$ 内，找出两个整数 $x$ 和 $y$（$l \le x < y \le r$），使 $C(x) \mathop{\&} C(y)$ 字典序最小，并输出该积前 $n$ 个二进制符号。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例数量。 每组测试用例包含一行，含三个整数 $l$，$r$，$n$（$1 \le l < r < 2^{30}$；$1 \le n \le 1000$），表示可选取的数字区间及输出长度。

对于每组测试用例，输出一行长度为 $n$ 的二进制字符串，表示字典序最小的闭包积的前 $n$ 位。

在第一个样例中，字典序最小的字符串由 $C(2) \mathop{\&} C(4)$ 得到。 由 ChatGPT 5 翻译