Problem J48: Infinite Powers of 10 / 无限次幂

版权信息： · 数列模拟与位分析

---

任务总览

任务名称	时间限制	内存限制	分数
无限次幂	1 sec	1024 MB	15 points

---

题目描述

考虑将所有 $10$ 的非负整数次幂按顺序连接起来： $10 ^ 0$ = 1, $10 ^ 1$= 10, $10 ^ 2$ = 100,$ $10 ^ 3 = 1000$, $\quad \dots$连接后的数列如下：

1101001000...

你需要判断该无限序列的第 $N$ 位是 0 还是 1。

---

输入格式

*第 $1$ 行为一个整数 $T$（$1 \leq T \leq 10000$），表示测试数据组数；

• 接下来的 $T$ 行，每行一个整数 $N$（$1 \leq N \leq 10 ^ 9$），表示需要查询的位置。

---

输出格式

*输出共 $T$ 行；

• 每行一个字符 0 或 1，表示该位在数列中对应的值。

---

输入输出样例

输入示例

3
1
2
3

输出示例

1
1
0

---

题目分析与解法

✅ 数列构造过程：

连接的数列为：

10 ^ 0 = 1       → 1 位
10 ^ 1 = 10       → 2 位
10 ^ 2 = 100       → 3 位
10 ^ 3 = 1000       → 4 位
10 ^ 4 = 10000       → 5 位
...

所以构成的整体数列为：

1 | 10 | 100 | 1000 | 10000 | ...

我们只需：

1. 逐步累加每个 $10 ^ k$ 的长度；
2. 找出 $N$ 落在哪个幂中；
3. 然后从该项 $10 ^ k$ 中定位该位，判断是 1 还是 0。

✅ 示例说明：

• 第 $1$ 位是 $10 ^ 0 = 1$ → 输出 1
• 第 $2$ 位是 $10 ^ 1 = 10$ → 输出 1
• 第 $3$ 位是 $10 ^ 1 = 10$ 的第二位 → 输出 0

---

边界细节说明

*数列中 10^k 的位数为 $k + 1$；

• 最大查询位置为 $10 ^ 9$，需高效判断；
• 可预先构建每段的起始下标，然后使用二分查找定位。

---

时间复杂度分析

操作	复杂度
每次查询	$O(\log N)$
总体查询	$O(T \cdot \log N)$，$T \leq 10000$

---