如何优化解决这个数学序列的类

Question

1,1 2,1 2 3 4,1 2 3 4 5,1 2 3 4 5 6,1 2 3 4 5 6 7 7,1 2 3 4 5 6 7 8 9 1 0,1 2 3 4 5 6 7 8 9 1 0 1 1 1,1 2 3 4 5 6 7 8 9 1 0 1 1 1,1 2 3 4 5 6 7 8 9 1 0 1 1.........

给我一个索引(1<=index<=10^10)，我需要找到该索引中的数字。

我已经写了这个工作代码，但它太慢了。我已经尽可能地优化了它，但仍然不够。有没有其他方法可以让它跑得更快？

public class Foo {

    private static Scanner sc = new Scanner(System.in);
    private static long input;
    private static long inputCounter = 0;
    private static int numberOfInputs;


    public static void main(String[] args) {
        numberOfInputs = Integer.parseInt(sc.nextLine().trim());

        while (inputCounter != numberOfInputs) {
            input = Long.parseLong(sc.nextLine().trim());
            System.out.println(step());
            inputCounter++;
        }
    }

    public static char step() {
        int incrementor = 1;
        long _counter = 1L;

        while (true) {
            for (int i = 1; i <= incrementor; i++) {
                _counter += getNumberOfDigits(i);

                if (_counter > input) {
                    return ((i + "").charAt((int)(input - _counter
                            + getNumberOfDigits(i))));
                }
            }
            incrementor++;
        }
    }

    private static long getNumberOfDigits(int n) {
        // 5 or less
        if (n < 100) {
            // 1 or 2
            if (n < 10)
                return 1;
            else
                return 2;
        } else {
            // 3 or 4 or 5
            if (n < 1000)
                return 3;
            else {
                // 4 or 5
                if (n < 10000)
                    return 4;
                else
                    return 5;
            }
        }
    }
}

Edit2:一些示例I/O：

1 : 1
2 : 1
3 : 2
4 : 1
5 : 2
6 : 3
7 : 1
8 : 2
9 : 3
10 : 4
11 : 1
12 : 2
13 : 3
14 : 4
15 : 5
16 : 1
17 : 2
18 : 3
19 : 4
20 : 5
21 : 6
22 : 1
23 : 2
24 : 3
25 : 4
26 : 5
27 : 6
28 : 7
29 : 1
30 : 2
31 : 3
32 : 4
33 : 5
34 : 6
35 : 7
36 : 8
37 : 1
38 : 2
39 : 3
40 : 4
41 : 5
42 : 6
43 : 7
44 : 8
45 : 9
46 : 1
47 : 2
48 : 3
49 : 4
50 : 5
51 : 6
52 : 7
53 : 8
54 : 9
55 : 1
56 : 0
57 : 1
58 : 2
59 : 3
60 : 4
61 : 5
62 : 6
63 : 7
64 : 8
65 : 9
66 : 1
67 : 0
68 : 1
69 : 1
70 : 1
71 : 2
72 : 3
73 : 4
74 : 5
75 : 6
76 : 7
77 : 8
78 : 9
79 : 1
80 : 0
81 : 1
82 : 1
83 : 1
84 : 2
85 : 1
86 : 2
87 : 3
88 : 4
89 : 5
90 : 6
91 : 7
92 : 8
93 : 9
94 : 1
95 : 0
96 : 1
97 : 1
98 : 1
99 : 2

Answer 1

我认为三角形数字在这里起作用，如果我们看一下数字的位置：

Position: 1  2 3  4 5 6  7 8 9 10  11 12 13 14 15,  16 17 18 19 20 21,  22 23 24 25 26 27 28 
Number:   1, 1 2, 1 2 3, 1 2 3 4,  1   2  3  4 5,    1  2  3  4  5  6,  1   2  3  4  5  6  7, 

把这个序列称为N(p)。

现在看一下公式为k(k+1)/2的三角形数

k            :  1   2    3    4    5     6
k(k+1)/2     :  1   3    6   10   15    21      triangle numbers
k(k+1)/2+1   :  2   4    7   11   16    22      plus one
N(k(k+1)/2+1):  1   1    1    1    1     1      item at this position

0.5 x^2 + 0.5 x + 1 - p = 0.

x = -0.5 +/- sqrt( 0.25 - 2 * (1-p) )

1    0
2    1
3    1.5615528128
4    2
5    2.3722813233
6    2.7015621187
7    3
8    3.2749172176
9    3.5311288741
10   3.7720018727
11   4
12   4.216990566
13   4.4244289009
14   4.623475383
15   4.8150729064
16   5

所以如果我们取k=flood(-0.5+/-sqrt(2p-1.75))，我们就会找到这个数字k。接下来，求出l=p-k(k+1)/2，给出第p位的数字。

正如所指出的，一旦我们得到两位数的数字，这就失败了。但我们可以做个调整。我们可以得到一个公式“三角形数字”TD(k)。它的行为类似于三角形数T(k)，对于k<10，但是增加了额外的数字。

k     : 1  ...  9  10  11  12
T(k)  : 1      45  55  66  78
change              1   3   6
TD(k) : 2      45  56  69  84

我们看到，对于10<=k<=99，我们只需要加上T(k)+T(k-9)。这应该给我们另一个二次型，我们可以解决。对于100<=k<=999，T(k)+T(k-9)+T(k-99)也发生类似的情况。

Now T(k)+T(k-9) + 1 = k(k+1)/2 +(k-9)(k-8)/2 + 1
                     = 0.5 k^2 + 0.5 k + 0.5 k^2 - 17/2 k + 72/2 + 1
                     = k^2 -8 k + 37 

x = ( 8 +/- sqrt(64 - 4 *(37-p) ) ) /2
  = ( 8 +/- sqrt(4 p - 64) )/2
  =   4 +/- sqrt(p - 21)