思路:
1. i属于哪个区间[10^(k-1),10^k-1], 也就是n那个区间有几位数
    long long map[]={0,45,9045,1395495,189414495,(long long)(2E31-1)};
   我另外写了个程序算出来的..汗

2. i<=map[k], 纸上算出来一个式子, 根据h可以得出map[k]某个区间里第h行的末尾是第n个digits, 比如
123..9899100
123..9899100101
123..9899100101102
123..9899100101102103
当h=4时(第4行), n等于([103的3]到开始[123的1]有多少位digits)
反过来可以由已知的n求出h
这个h不一定是整数, 但是由于函数n=f(h)是递增的, 所以根据h的整数位可以得出要求的digit在哪一行内

h=sqrt(2*n/k+(0.5+map2[k-1]/k)^2-0.5-map2[k-1]/k
map2[k]存放了 1234..k个9有多少位数


3. 根据行数算出要求的digit是哪一行的第几位, 现在问题简化成求123..9899100..这个数列中的第几位数, 很简单了

注意第2步中
开方下来h如果是整数需要特别判断一下, 我在这磨了好久.. 因为开始试图用(int)(h-0.00001)这种方式判断整数纠缠不清.. 非常傻. 就想不起来直接判断

(实验了一下math.h的sqrt()函数对于整数的开方没有误差25.0000开方就是5.0000, 可以直接if(5==5.0000)这样)

小弟拙见..希望没有浪费大家时间


代码: (为什么用c++就WA..g++就能过, 怎么试都试不出来 高手请指点..)
#include <stdio.h>
#include <math.h>

long long pow10(long long n) {
    long long a;
    a=1;
    while(n--)
        a*=10;
    return a;
}

int main() {
    long long map[]={0,45,9045,1395495,189414495,(long long)(2E31-1)};
    long long map2[]={0,9,189,2889,38889};  //how many digits does {1 2 3 4 ... 99...9} have
    long long N,n,k,x,l,number,result,digit,k_;
    double h;
    scanf("%lld",&N);
    while(N--) {
        scanf("%lld",&l);
        for(k=1;l>map[k];k++);
        n=l-map[k-1];
        h=sqrt((double)2*n/k+(0.5+(double)map2[k-1]/k)*(0.5+(double)map2[k-1]/k))-0.5-(double)map2[k-1]/k;

        if(h==(int)h)
            x=h;
        else
            x=(int)h+1;
        n=n-map2[k-1]*(x-1)-(x-1)*x/2*k;
        for(k_=1;map2[k_]<n;k_++);   //area's number of digits
        n-=map2[k_-1];
        number=pow10(k_-1)+(n-1)/k_;
        digit=k_-(n-1)%k_;
        result=number/pow10(digit-1)%10;
        printf("%lld\n",result);
    }
    return 0;
}

• 同意楼上的思路，给出Java源码 (1483) goslingL 2010-07-29 13:17:38
• Re:O(1)终于搞出来了.. (15) 740340735 2011-07-31 13:32:11
• Re:O(1)终于搞出来了.. (34) iheng_scau 2012-09-18 20:43:25