咕咕东的奇妙序列

题意：

咕咕东 正在上可怕的复变函数，但对于稳拿A Plus的 咕咕东 来说，她早已不再听课，此时她在睡梦中 突然想到了一个奇怪的无限序列：112123123412345 …这个序列由连续正整数组成的若干部分构成，其 中第一部分包含1至1之间的所有数字，第二部分包含1至2之间的所有数字，第三部分包含1至3之间的所 有数字，第i部分总是包含1至i之间的所有数字。所以，这个序列的前56项会是 11212312341234512345612345671234567812345678912345678910，其中第1项是1，第3项是2，第20项是 5，第38项是2，第56项是0。咕咕东 现在想知道第 k 项数字是多少！但是她睡醒之后发现老师讲的东西 已经听不懂了，因此她把这个任务交给了你。

输入格式：
输入由多行组成。
第一行一个整数q表示有q组询问
接下来第i+1行表示第i个输入 ，表示询问第 项数字。

输出格式：
输出包含q行
第i行输出对询问 的输出结果。

数据范围：

样例输入：

5 1 3 20 38 56

样例输出：

1 2 5 2 0

思路：

题意分析：
这道题数据量挺大，单纯暴力求解肯定不太行，但前3组的数据量不大，可以骗分。
对于大数据量开始观察数据特点，将1看成一个小组，12看成第二个小组，123看成第三个小组依次进行下去，可以发现前9个小组的最大值都是一位数，每组的数位为公差为1的等差数列，将前9个小组看成一个大组，由等差数列求和公式可得第一大组的数位和b[1]=45，同时记录拥有第一大组最大值的第9小组的位数a[1]=9。依次进行下去，可知第二大组为10-99，每组的数位为公差为2的等差数列，由公式计算得第二大组的数位总数b[2]=9045，同时第99小组的位数a[2]=189，按照上面的思路进行下去，其实每个大组的差别就是包含的小组中最大值的位数不相等，即每个大组的方差不一样。
这样计算下去九个大组位数超过1e18，所以这里设了a[10],b[10]，但是这里有个问题b[9]数据量太大了，已知上限为1e18，所以这里用上限代替实际的大数值。

具体实现：
每次查找第k位，先确定它位于哪个大组，即与b[i]进行比较。k减去所在大组前面的位数之后可以得到在当前大组中的位数，同时得到该数据所处大组中的上下界。
在一个大组中查找k这时数据量还是十分庞大，怎么简化操作？由于一个大组中每个小组的位数都是有序的（相差方差个），所以可以使用二分法。
在大组中通过二分查找每一个小组的位数，确定k所在的小组。
一个小组内还可以继续分组，同样位数有序可以继续使用二分法继续查找，减去前面的a[i]剩余的是与其位数相等的数，在这里面确定是第几个数字的第几位。

关键点：
上面的实现还挺啰嗦的，其实关键点就是找到每组数据之间关系吧（等差啊，求和啊，是数学问题）。
再就是数据量挺大的，简化操作，能够想到用二分。
再就是数据范围 long long，仔细一点不要因为一个顺手写成int然后找半天错误找不出来。
最后的最后，实在做不出来的时候前三个点还能骗点分。

代码：

#include<cstdio>
#include<cmath>
using namespace std;

long long a[10],b[10];					//a[i]记录最大i位数那一小组的位数
                                            //b[i]记录直到最大i位数的数位
long long k,c,ans;

void toNum(long long x){
	long long t1=x,t2=0;  c=0;
	while(t1>0){t2++;t1/=10;}							//t2记录数的位数
	for(long long i=1;i<t2;i++)
		 c+=i*(pow(10,i)-pow(10,i-1)); 					//求位数小于x的数的位数和
	c+=(x-pow(10,t2-1)+1)*t2;						//加上位数和x相同的数的位数 
}

void solve(long long x,int y){
	long long t1=(x-2)*c+(x-2)*(x-3)*y/2;				//记录最大值为x-1前面的位数 
	long long t2=(x-1)*c+(x-1)*(x-2)*y/2;				//x前面的位数 
	long long t3=x*c+(x-1)*x*y/2; 						//x+1
	if(k<=t2) {k-=t1;x-=1;}
	else if(k<=t3) k-=t2;
	else {k-=t3;x+=1;}
	long long p=0;
	for(long long i=1;i<=9;i++){
		if(k<=a[i]){
			k-=a[i-1];p=i;break;						//在与待查找的数字有相同位数的数字中查找 
		}
	}
	long long v1=k/p; long long v2=k%p;
	if(v2==0) x=pow(10,p-1)+v1-1;
	else{
			x=pow(10,p-1)+v1;
			long long j=p-v2;
			x=x/pow(10,j);
		}
	ans=x%10;
}

int main(){
	int q;
	scanf("%d",&q);
	for(long long i=1;i<=9;i++)
		a[i]=a[i-1]+i*(pow(10,i)-pow(10,i-1));
	long long u=1;
	for(long long i=1;i<=9;i++){
		u*=10;
		long long n=u-u/10;
		b[i]=n*i+n*(n-1)*i/2+n*a[i-1]+b[i-1];
	}   
	for(int i=0;i<q;i++){
		scanf("%lld",&k);
		int w=0;
		for(int j=1;j<=9;j++){
			if(k<=b[j]){
				w=j;							//记录是在几位数的区间里
				k-=b[j-1];break;								 
			}
		}
		long long l=1,r=pow(10,w)-pow(10,w-1),mid=0;                 //i位数的左右端点，i位数有r个 
		toNum(pow(10,w-1));								//t1=mid的位数 
		while(l<=r){								
			mid=(l+r)/2;
			long long t1=mid*c+mid*(mid-1)*w/2;						//确定在最大值为几的组内 
			if(t1<k)  l=mid+1;
			else r=mid-1;
		}
		solve(mid,w);
		printf("%d\n",ans);
	}
	return 0;
}