Очень красивая классная задача. Решается немного длинно, зато решение очень быстрое.
В формулировке задачи определена возрастающая последовательность C(i)
и требуется вычислить определённый её элемент. Номер элемента не превосходит 10^7
, что позволяет построить всю последовательность до нужного элемента за время сравнимое с одной секундой. Это простое решение, но это ложный след. C(i)
можно вычислить не строя все предшествующие элементы.
Математика
В пару к функции n = C(i)
определим функцию i = D(n)
- количество элементов последовательности C
не больших чем n
. D(n)
не убывает.
По i
отыщем k
такое что D(2^k) < i <= D(2^(k + 1))
. Затем двоичным поиском отыщем n
такое что D(n - 1) < i <= D(n)
. Тогда верно что С(i) = n
.
Как вычислить D(n)
? Нужно сложить количество полных квадратов не больших n
и количество полных кубов. При этом некоторые числа мы учтём два раза. Это числа которые и квадраты и кубы. Можно убедится что все такие числа - шестые степени. Определим функцию root(n, b)
- число степеней порядка b
не превосходящих n
. Тогда D(n) = root(n, 2) + root(n, 3) - root(n, 6)
.
Функция root(n, b)
вычисляется аналогично C(i)
: отыщем k
такое что (2^k)^b <= n < (2^(k + 1))^b
. Двоичным поиском отыщем r
такое что r^b <= n < (r + 1)^b
. r
- искомое значение.
Функцию root
можно вычислить с помощью вещественной арифметики и после уточнить, я выбрал другой способ чтобы не иметь проблем с точностью и ограниченной разрядностью вещественных чисел.
Код
def bsearch(n, f):
low = 1
high = 2
while f(high) <= n:
low, high = high, 2 * high
assert f(low) <= n < f(high)
while low < high - 1:
mid = (low + high) // 2
assert low < mid < high
if f(mid) <= n:
low = mid
else:
high = mid
assert f(low) <= n < f(high)
assert low + 1 == high
return low
def root(n, b):
return bsearch(n, lambda i: i ** b)
def d(n):
return root(n, 2) + root(n, 3) - root(n, 6)
def c(n):
if n == 1:
return 1
return bsearch(n - 1, d) + 1
print(c(int(input())))
$ echo 1 | python ith_item.py
1
$ echo 4 | python ith_item.py
9
$ time echo 10000000 | python ith_item.py
99080961339364
real 0m0.033s
user 0m0.028s
sys 0m0.004s
P.S. Обнаружилась закономерность:
i C(i)
1 1
10^ 3 837225
10^ 6 980426727225
10^ 9 998004326672772225
10^12 999800043326667277722225
10^15 999980000433326666727777222225
10^18 999998000004333326666672777772222225
10^21 999999800000043333326666667277777722222225
10^24 999999980000000433333326666666727777777222222225
10^27 999999998000000004333333326666666672777777772222222225
10^30 999999999800000000043333333326666666667277777777722222222225
10^33 999999999980000000000433333333326666666666727777777777222222222225
10^36 999999999998000000000004333333333326666666666672777777777772222222222225
10^39 999999999999800000000000043333333333326666666666667277777777777722222222222225
10^42 999999999999980000000000000433333333333326666666666666727777777777777222222222222225
10^45 999999999999998000000000000004333333333333326666666666666672777777777777772222222222222225
10^48 999999999999999800000000000000043333333333333326666666666666667277777777777777722222222222222225
10^51 999999999999999980000000000000000433333333333333326666666666666666727777777777777777222222222222222225
10^54 999999999999999998000000000000000004333333333333333326666666666666666672777777777777777772222222222222222225