这道题其实不难，就是有些绕。题目给了一个数字序列的规律，要求输出数字序列第i位数字。第一次没注意输出了第i个数字wa了。eg: …12345678910…，第10位数字是1。解题过程就两点：1是找到第i位对应的子串，2是找到子串中对应的数字并输出。

Description: A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.
For example, the first 80 digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)

Output

There should be one output line per test case containing the digit located in the position i.

Sample Input

1
2
3
2
8
3

Sample Output

1
2
2
2

题目还需要明白如下知识点：

  • 如何计算某一个子串的长度，(int)(log10((double)i)+1)；

  • 假设第i位数字位于第m个子串的第n位，那么问题就可以简化为找到长度>n的子串$S_k$，求它的第n位。我们可以找到长度>n的最小子串$S_k$，假设$S_k$的长度是len，那么$k/(10^{len-n})$就是所求。为啥呢？因为可以明确一点，当我们找到了长度>n的最小子串$S_k$之后，所求的位数数字肯定是k的某一位，因为如果是k-1的某一位，那么长度>n的最小子串就是$S_{k-1}$了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cmath>
using namespace std;

const int N=31270;

long a[N];
long sum[N];

void makeT(){
	a[1]=1;
	sum[1]=1;
	for(int i=2;i<N;i++){
		a[i]=a[i-1]+(int)(log10((double)i)+1);
		sum[i]=sum[i-1]+a[i];
	}
}

int pow_10(int x, int d)
{
	while (d--) x /= 10;
	return x % 10;
}

int main(){
	makeT();
	int n,str_idx;
	long k,idx,len,cnt,j;
	while(cin>>n){
		for(int i=0;i<n;i++){
			cin>>k;
			str_idx=0;
			while (sum[str_idx] >= 0 && sum[str_idx] < k) str_idx++;
			len=k-sum[str_idx-1];
			j = 0;
			while (a[j] < len) j++;
			cout<<pow_10(j,a[j]-len)<<endl;
		}
	}
	return 0;
}

参考：