题目
思路就是做两次二分，然后确定所在的数字，样例都没问题
#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<iomanip>
#include<math.h>
#include<vector>
#define MAX 1e17
#define int long long
using namespace std;
int sum2[114];
vector<int> sum;
int p10[30],k;
int check(int bit,int n){//位数和第几个数
int a_1=sum2[bit-1]+bit,S;
S=n*a_1+n*(n-1)/2*bit;
return S;
}
signed main(){
p10[0]=1;
for(int i=1;i<=21;i++) p10[i]=p10[i-1]*10;
sum.push_back(0);
for(int i=1;i<=17;i++){//预处理
int n=p10[i]-p10[i-1];
sum2[i]=n*i+sum2[i-1];
if(i<=9) sum.push_back(n*(sum2[i-1]+i)+n*(n-1)/2*i+sum[i-1]);
}
int t;
cin>>t;
while(t--){
cin>>k;
int pos=lower_bound(sum.begin(),sum.end(),k)-sum.begin();
k-=sum[pos-1];
int l=1,r=p10[pos]-p10[pos-1];
while(l<r){//二分以哪个数结尾
int mid=(l+r)>>1;
if(check(pos,mid)<k) l=mid+1;
else r=mid;
}
k-=check(pos,l-1);
int i=1;
while(k-sum2[i]>0) i++;
k-=sum2[i-1];
int tail=p10[i-1]+k/i-1,mod=k%i,dig;//确定所在的数字
if(!mod) mod=i;mod=i+1-mod;
for(int j=1;j<=mod;j++){
dig=tail%10;
tail/=10;
}
cout<<dig<<endl;
}
return 0;
}