Digit Queries

题目描述

Consider an infinite string that consists of all positive integers in increasing order:
12345678910111213141516171819202122232425...

Your task is to process q queries of the form: what is the digit at position k in the string?

输入

The first input line has an integer q（1 ≤ q ≤ 1000）: the number of queries.
After this, there are q lines that describe the queries. Each line has an integer k（）: a 1-indexed position in the string.

输出

For each query, print the corresponding digit.

样例输入

3
7
19
12

样例输出

7
4
1

思路分析

自然数按位数分组，确定k所在区间，找出k定位到的自然数。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int q;
ll k;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>q;while(q--){cin>>k;ll d=9,w=1,total_d,total_w,ans;total_w=d*w;total_d=d;while(k>total_w){d*=10;w++;total_w+=d*w;total_d+=d;}ll diff=(k-(total_w-d*w))%w;ll n=(k-diff-(total_w-d*w))/w;ll st=pow(10,w-1);for(ll i=2;i<=n;i++){st++;}if(diff==0){ans=st%10;}else{st++;for(int i=1;i<=w-diff;i++){st/=10;}ans=st%10;}cout<<ans<<"\n";}return 0;
}