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

古城微笑少年丶 2022-01-05 15:29 197阅读 0赞

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

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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]='\0';
    59       if(position==value_bit)
    60         printf("%c\n",str[0]);
    61       else
    62         printf("%c\n",str[position-1]);
    63 
    64     }
    65     return 0;
    66 }

转载于:https://www.cnblogs.com/sdau--codeants/p/3384755.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/5bdbd36434f24e74a210b2c3bc2b42c5.png