奇妙的序列

问题描述

有一个奇怪的无限序列: 112123123412345...... 
这个序列由连续正整数组成的若干部分构成，其中第一部分包含 1 至 1 之间的所有数字，第二部分包含 1 至 2 之间的所有数字，第三部分包含 1 至 3 之间的所有数字，第 i 部分总是包含 1 至 i 之间的所有数字。
所以，这个序列的前 56 项会是11212312341234512345612345671234567812345678912345678910，其中第 1 项是 1，第 3 项是 2，第 20 项是 5，第 38 项是 2，第56项是 0。
求第 k 项数字是多少。

Input

输入由多行组成。
第一行一个整数 q 表示有 q 组询问 (1 ≤ q ≤ 500)
接下来第 i+1 行表示第 i 个输入 ki，表示询问第 ki 项数字 (1 ≤ ki ≤ 1e18)

Output

输出包含 q 行
第 i 行输出对询问 ki 的输出结果。

Sample

Input: 
5
1
3
20
38
56

Output: 
1
2
5
2
0

数据范围

数据点	q (上限)	k (上限)
1, 2, 3	500	55
4, 5, 6	104	106
7, 8, 9, 10	500	1018

Limitation

Time limit		1000 ms
Memory limit	65536 kb

解题思路

源代码

暴力代码，只有60%的分。

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main() {
	string a;
	stringstream b;
	for (int i = 1; i < 100000; i++) {
		b << i;
	}
	b >> a;
	int n;
	cin >> n;
	cout << a[n - 1] << endl;
	return 0;
}