题目链接：
http://poj.org/problem?id=1019
题目大意：
Sk表示123...k
把S1S2S3...Sk排成一行 比如：112123123412345123456....
求第i个数字是多少。
解题思路：
如果Sk表示123...k所占的位数，显然Sk=Sk-1+Cal(k)。Cal(k)表示k的位数。
先打表预处理sum[i]=S1+S2+..+Si;
然后在sum[i]中查找第n个属于哪一个Sk.
在同一个Sk中，一位有1~9 9个，2位有10~99 90个 3位有100~999 900个。。。所以可以先找到属于该Sk中的第几位的数。
找到位数后，就可以算出属于该位的第几个数了 比如四位的第一个数1000，第二个数为1001，，，
找到该位数的第几个后，再找属于该数的第几位，比如1234的第二位是2.
代码：
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
ll Cal(ll k) //计算k的位数
{
ll res=0;
while(k)
{
res++;
k/=10;
}
return res;
}
ll cnt[33000]; //cnt[i]表示S1S2...Si的总位数
ll bitcnt[20]; //在一个Si中，bitcnt[i]表示1~i位总共的个数
ll shi[12]; //shi[i]表示10^(i-1);
int fun(int x,int num) //计算x的第num位数字
{
int res=0,temp=x;
while(temp)
{
res++;
temp/=10;
}
res=res-num+1;
for(int i=1;i<res;i++)
x/=10;
return x%10;
}
int main()
{
ll lim=2147483647LL; //打表预处理
cnt[1]=1;
ll la=1;
for(int k=2;cnt[k-1]<=lim;k++)
{
la=la+Cal(k); // Sk=S(k-1)+k的位数
cnt[k]=cnt[k-1]+la;
}
int up=31268; //计算知k最大为31268
bitcnt[1]=9;
la=1;
for(int i=2;i<10;i++) //计算1~i位总的个数 1 有9个 2位有90个 3位有900个
{
la*=10;
bitcnt[i]=bitcnt[i-1]+la*9*i;
}
shi[1]=1;
for(int i=2;i<=10;i++)
shi[i]=shi[i-1]*10;
ll n;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%I64d",&n);
int k=lower_bound(cnt+1,cnt+up+1,n)-cnt; //求出是属于第k个数中
int gap=n-cnt[k-1]; //中间差多少位
int bb=lower_bound(bitcnt+1,bitcnt+9+1,gap)-bitcnt;//算出数位
gap-=bitcnt[bb-1];//算出是该数位的第几个数
int a=(gap%bb)?(gap/bb+1):(gap/bb); //表示第几个
int b=gap%bb; //表示是该数的第几位
if(b==0)
b+=bb;
printf("%d
",fun(shi[bb]-1+a,b));
}
return 0;
}