P17726 最短公共超串？

本题征集**人类**题解。

给定正整数 $n$（$n \ge 10$），求将 $1, 2, \ldots, n$ 视作无前导零的十进制数码串后，这些数码串的最短公共超串的长度 $L(n)$。 :::info[最短公共超串] 对于有限个字符串 $S_1, S_2, \ldots, S_k$，若字符串 $T$ 含有每个 $S_i$（$1 \le i \le k$）作为连续子串，则称 $T$ 为它们的公共超串。 $S_1, S_2, \ldots, S_k$ 的最短公共超串是满足条件的 $T$ 中长度最短的那些。由于 $S_1 S_2 \cdots S_k$（即将每个 $S_i$ 顺次拼接）是它们的一个公共超串，它们的最短公共超串总是存在。所有的最短公共超串的长度相同。 :::

**本题包含多组测试数据。** 第一行，一个正整数 $T$，表示测试数据组数。对于每组测试数据： - 第一行，一个正整数 $n$。

对于每组测试数据，输出一行，一个整数 $L(n)$，表示最短公共超串的长度。

**【样例解释 \#1】** 对于 $n = 21 \sim 30$，对应的一个最短公共超串分别是： - $101120131415161718219$； - $1011201314151617182219$； - $101120131415161718219223$； - $10112013141516171821922324$； - $1011201314151617182192232425$； - $101120131415161718219223242526$； - $10112013141516171821922324252627$； - $1011201314151617182192232425262728$； - $101120131415161718219223242526272829$； - $1011201301415161718219223242526272829$。 长度分别为 $21, 22, 24, 26, 28, 30, 32, 34, 36, 37$。 **【数据范围】** **本题各个测试点的分数不等。** | 测试点编号 | $T$ | $n$ | 特殊性质 | 分数 | |:--:|:--:|:--:|:--:|:--:| | $1 \sim 41$ | $= 1$ | $= 9 \hspace{4mu} +$ 测试点编号 | 无 | $1$ | | $42$ | $= 50$ | $\le 100$ | ^ | $10$ | | $43$ | $\le 1000$ | $\le 1000$ | ^ | $5$ | | $44$ | $\le 10^5$ | $\le 10^5$ | ^ | $5$ | | $45$ | ^ | $\le 10^{18}$ | A | $5$ | | $46$ | ^ | ^ | B | $5$ | | $47$ | ^ | ^ | C | $5$ | | $48$ | ^ | ^ | D | $5$ | | $49$ | ^ | ^ | E | $9$ | | $50$ | ^ | ^ | 无 | $10$ | - 特殊性质 A：存在正整数 $k$ 使得 $n = 10^k$。 - 特殊性质 B：存在正整数 $k$ 使得 $n = 10^k - 1$。 - 特殊性质 C：存在正整数 $k$ 使得 $n = 10^k + 1$。 - 特殊性质 D：存在正整数 $k$ 使得 $n = 2 \times 10^k - 1$。 - 特殊性质 E：存在正整数 $k$ 使得 $n \in [0.99 \times 10^k, 10^k]$。 对于所有测试点，$1 \le T \le 10^5$，$10 \le n \le 10^{18}$。