Number Sequence 无算法，靠思想数学题

Problem 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

***************************************************************************************************************************

 1 /*
 2 一个数的位数可用log10((double)value)+1表示
 3 a[]表示子串的长度，b[]表示到第i个子串时的总长度
 4 */
 5 #include<iostream>
 6 #include<string>
 7 #include<cstring>
 8 #include<cmath>
 9 #include<cstdio>
10 #include<queue>
11 #include<cstdlib>
12 #define maxn  32000
13 using namespace std;
14 typedef  long  LL;
15 unsigned int a[maxn],b[maxn];
16 unsigned int n,m,j,k;
17 unsigned int cas;
18 int main()
19 {
20     a[0]=0;
21     b[0]=0;
22     a[1]=1;
23     b[1]=1;
24     LL i;
25     for(i=2;i<maxn;i++)
26     {
27         a[i]=a[i-1]+log10((double)i)+1;
28         b[i]=b[i-1]+a[i];
29     }
30     scanf("%u",&cas);
31     while(cas--)
32     {
33       scanf("%u",&n);
34       for(j=0;j<maxn;j++)
35       {
36           if(n<=b[j])
37             break;
38       }
39       unsigned int remain=n-b[j-1];
40       unsigned int sum=0,value;
41       for(value=1;value<maxn;value++)
42       {
43           sum+=(1+log10((double)value));
44           if(sum>=remain)
45             break;
46       }
47       unsigned int value_bit=1+log10((double)value);
48       unsigned int position=remain-(sum-value_bit);
49       unsigned int temp1=value;
50       char* str = (char*)malloc(10*sizeof(char));
51       unsigned int num=0;
52       while(temp1)
53       {
54           unsigned int temp=temp1%10;
55           str[num++]=temp+'0';
56           temp1/=10;
57       }
58       str[num]='';
59       if(position==value_bit)
60         printf("%c
",str[0]);
61       else
62         printf("%c
",str[position-1]);
63 
64     }
65     return 0;
66 }

View Code

Number Sequence 无算法，靠思想 数学题

Number Sequence 无算法，靠思想数学题