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（1 ≤ k ≤ 1018）: a 1-indexed position in the string.

输出

For each query, print the corresponding digit.

样例输入

复制

3
7
19
12

样例输出

复制

7
4
1

如果用 k=1（未减 1）计算：

• 数字位置 = 10 + (1 / 2) = 10 + 0 = 10（正确）

• 数字内的位置 = 1 % 2 = 1（错误，实际是第 1 位）

如果用 k-1=0 计算：

• 数字位置 = 10 + (0 / 2) = 10 + 0 = 10（正确）

• 数字内的位置 = 0 % 2 = 0（正确，对应字符串 "10" 的第 0 位，即 '1'）

代码 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int q;void solve(ll k)
{ll w=1;//位数ll num=9;//该位数数字个数 1-9，2-90ll s=1;while(k>w*num){k-=w*num;w++;num*=10;s*=10;		}ll x=s+(k-1)/w; //2位数第7个，10+8/2=14，第6个 10+7/2=13ll p=(k-1)%w;cout<<to_string(x)[p]<<'\n';
}int main()
{	cin>>q;while(q--){ll k;cin>>k;solve(k);}return 0;
}