题解

思路

令 $p=10^i$。

做法

把平方根的位数和 $x$ 的位数分类比较，前缀区间与平方根区间有交集时，合法的 $x$ 恰好组成 $[1,1]$，以及对每个 $1\le i\le9$ 的单点 $[p^2-2p,p^2-2p]$ 和连续区间 $[p^2-p,p^2+p-1]$。这些区间两两不交：平方根比 $p$ 更大或比 $p-2$ 更小时，由平方根决定的范围与由十进制前缀决定的范围已经错开。

预处理这 $19$ 个区间。对每个 $N$，把每个区间与 $[1,N]$ 的交集长度相加即为答案。

复杂度

每组测试只需常数次计算，总时间复杂度为 $O(T)$，空间复杂度为 $O(1)$。