posts - 100,  comments - 15,  trackbacks - 0

#include<iostream>
#include
<cmath>
using namespace std;
#define M 40000
__int64 sum[M
+1];
__int64 len[M
+1];
void init()
{
    
int i;
    len[
0]=0;
    sum[
0]=0;
    
for(i=1;i<=M;i++)
    
{
        len[i]
=len[i-1]+(int)log10(double(i))+1;
        sum[i]
=sum[i-1]+len[i];
    }


}

int search(__int64 n)
{
    __int64 k,w,li,i,j;
    k
=1;
    
while(sum[k]<n) k++;//di k zu
    w=n-sum[k-1];//
    i=1;
    
while(w-int(log10(double(i))+1)>0
    
{
        w
-=int(log10(double(i))+1);
        i
++;
    }

    li
=(int)log10((double)i)+1;
    
for(j=1;j<=li-w;j++)
        i
/=10;
    
return i%10;
}


    
int main()
{
    init();
    
int t;
    __int64 n;
    
    scanf(
"%d",&t);

    
for(;t--;)
    
{
        scanf(
"%I64d",&n);
        printf(
"%d\n",search(n));
    }

    
return 0;
}


posted on 2009-07-28 09:43 wyiu 阅读(391) 评论(2)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理