# POJ 1019 Number Sequence

## Description

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.

For example, the first 80 digits of the sequence are as follows:

11212312341234512345612345671234567812345678912345678910123456789101112345678910

## Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)

## Output

There should be one output line per test case containing the digit located in the position i.

## Sample Input

2
8
3


## Sample Output

2
2


## 思路

a 保存当前序列位数，则 a[i]=a[i-1]+log10(i)+1 ;

s 保存前多少个序列总位数，则 s[i]=s[i-1]+a[i] ;

## AC 代码

#include<iostream>
#include<math.h>
using namespace std;
#define SIZE 31269              //这个数字是计算出来的，差不多刚好满足题目位数
unsigned a[SIZE],s[SIZE];
void init()
{
a[1]=s[1]=1;
for(int i=2; i<SIZE; i++)
{
a[i]=a[i-1]+log10(i)+1; //保存当前序列总位数
s[i]=s[i-1]+a[i];       //保存前i的序列位数和
}
}
int solve(unsigned n)
{
int i=1,len=0;;
while(s[i]<n)i++;           //根据s计算整数在第几个序列
int st=n-s[i-1];            //求出它在这个序列中的位置
for(i=1; len<st; i++)       //i代表当前位置的数字
len+=log10(i)+1;
return (i-1)/(int)pow(10,len-st)%10;    //返回结果
}
int main(void)
{
int N;
init();             //打表a s
cin>>N;
while(N--)
{
unsigned n;
cin>>n;
cout<<solve(n)<<endl;
}
return 0;
}


### 7 只已被捕捉

• 赵小轩 Mozilla FireFox | 59.0 Ubuntu

博主是男生还是女生啊……

• 千千 Chrome | 65.0.3325.181 Windows 10

当然是蓝孩子啦~

• 赵小轩 Mozilla FireFox | 59.0 Ubuntu

那么可爱的男孩纸，想要扑倒啊|´・ω・)ノ

• 千千 Chrome | 65.0.3325.181 Windows 10

所以……😝

• 贝尔静 Chrome | 49.0.2623.87 Windows XP

在这里

• 千千 猎豹安全浏览器 Windows 10

O(∩_∩)O哈哈~

• 千千 猎豹安全浏览器 Windows 10

是今天做的题目中唯一一个可以发出来的题目，其他做的题目嘛！都好简单啦~