终于0MS AC了，时间复杂度为O（1）
我的感觉是：算法虽然有点复杂，但很容易想到，编程时细心点很快就能AC
#include<stdio.h>
#include<math.h>
long pow10(long n)
{
if(n==0)return 1;
else if(n==1)return 10;
else if(n==2)return 100;
else if(n==3)return 1000;
else if(n==4)return 10000;
else if(n==5)return 100000;
else if(n==6)return 1000000;
else return -1;
}
#define MAX 4
int main()
{
int i,t,n,m;
long I,l[MAX],len[MAX],X,R,Xp,Y,r,y;
//compute l
l[0]=9;
for(i=1;i<MAX;i++)l[i]=l[i-1]+(i+1)*9*pow10(i);
//compute len
len[0]=l[0]*(l[0]+1)/2;
for(i=1;i<MAX;i++)len[i]=len[i-1]+9*pow10(i)*l[i-1]+(i+1)*9*pow10(i)*(9*pow10(i)+1)/2;
//input
scanf("%d",&t);
while(t--)
{
scanf("%ld",&I);
//Get X
//compute n
if(I<=len[0])n=1;
else if(I>len[MAX-1])n=MAX+1;
else
{
for(i=1;i<MAX;i++)
if(I<=len[i])
{
n=i+1;
break;
}
}
//compute X and R
if(n==1)
{
X=(long)((sqrt(1+8*(I-1))+1)/2);
R=I-X*(X-1)/2;
}
else
{
Xp=(long)((sqrt((n+2.*l[n-2])*(n+2.*l[n-2])+8.*n*(I-1-len[n-2]))+n-2*l[n-2])/(2*n));
X=Xp+pow10(n-1)-1;
R=I-len[n-2]+(1-Xp)*l[n-2]-Xp*(Xp-1)/2*n;
}
//Get Y
//compute m
if(R<=l[0])
{
m=1;
r=R;
}
else if(R>l[MAX-1])
{
m=MAX+1;
r=R-l[MAX-1];
}
else
{
for(i=1;i<MAX;i++)
{
if(R<=l[i])
{
m=i+1;
r=R-l[i-1];
break;
}
}
}
//compute Y and r
Y=(r-1)/m+pow10(m-1);
r=(r-1)%m+1;
//compute y and output
y=Y%((long)pow10(m-r+1))/((long)pow10(m-r));
printf("%ld/n",y);
}
return 0;
}