题解

思路

设 $N$ 的十进制长度为 $L$。

做法

位数少于 $L$ 的最大周期数是由 $L-1$ 个 9 组成的数（当该长度至少为 $2$）。对于恰有 $L$ 位的答案，其最短循环节长度 $d$ 必须是 $L$ 的真因子；固定 $d$ 后，为了尽量大，循环节只可能取 $N$ 的前 $d$ 位，若重复后超过 $N$，就把这段前缀减一再重复。

枚举 $L$ 的所有真因子，构造上述至多两个候选，与较短的全 9 候选一起取最大值。

复杂度

因为 $L\le18$，所有数都可放入 64 位整数；每组询问的时间复杂度为 $O(L^2)$，额外空间为 $O(L)$。