题目链接：

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\n",fun(shi[bb]-1+a,b));

   }

   return 0;

}