题目大意

考虑自然数构成的序列 $a$：$01234567891011\dots$，序列下标从 $0$ 开始，即 $a_0 =0, a_1 = 1$ 。
求 $a_n$（$0\le n\le 10^{18}$）。

解法

设 $a_n$ 所在的数字为 $x(n)$ 。
首先不难求出 $x(n)$ 的位数，设其为 $k$ 。
从而可以求出 $x(n)$ 是第几个 $k$ 位数，这样也就求出了 $x(n)$ 。
设 $x(n)$ 是第 $i$（$i\ge 1$）个 $k$ 位数，则有
$$ i = \left\lceil \frac{n+1 - s_{k-1}}{k}\right\rceil $$
$\lceil a/b \rceil$（$a\ge 0, b>0$）用代码可表示为(a + b - 1) / b。
其中，$s_{k-1}$ 表示「位数不超过 $k-1$ 的自然数」的位数之和。
进一步，可以求出 $a_n$ 在 $x(n)$ 第几位。
比较方便的办法是，把个位作为第 0 位，十位作为第 1 位，百位作为第 2 位，以此类推；
这样，x 的第 j 位可以表示为 x / pow(10, j) % 10。
设 $a_n$ 在 $x(n)$ 的第 $j$ 位，则有
$$ j = i k - (n +1 - s_{k-1}) $$

巴特西

hihoCoder #1349 Nature Numbers

题目大意

解法

最新文章

热门文章