нужно сократить время выполнения

Question

вот сама задача

Объединение последовательностей Даны две бесконечных возрастающих последовательности чисел A и B. i-ый член последовательности A равен i². i-ый член последовательности B равен i³.

Требуется найти C_x, где C — возрастающая последовательность, полученная при объединении последовательностей A и B. Если существует некоторое число, которое встречается и в последовательности A, и в последовательности B, то в последовательность C это число попадает в единственном экземпляре.

Входные данные
В единственной строке входного файла дано натуральное число x (1 ≤ x ≤ 10⁷).

Выходные данные
В выходной файл выведите C_x.

Примеры
входные данные
1
выходные данные
1

входные данные
2
выходные данные
4

входные данные
4
выходные данные
9

x = int(input())

c = []

for i in range(x+2):

    c.append(i**2)
    c.append(i**3)

c = list(set(c))

c.sort()

print(c[x])

Answer 1

Вот так раза в полтора быстрее. Только смысл?

c = set()
for i in range(x+2):
    i2 = i*i
    c.add(i2)
    c.add(i2*i)

c = sorted(c)

UPD Если нужен только последний элемент, то хранить всю последовательность (а тем более её сортировать) вовсе не нужно. Можно просто вычислить этот элемент.
Вот так на порядок быстрее:

def get_cx(x):
    i, j = 1, 1
    i2, j3 = 1, 1 # i**2, j**3
    k = 1
    while k <= x:
        if i2 == j3:
            i += 1
            i2 = i*i
            k -= 1
        elif i2 < j3:
            res = i2
            i += 1
            i2 = i*i
        else: # i2 > j3
            res = j3
            j += 1
            j3 = j*j*j
        k += 1

    return res

Answer 2

Очень красивая классная задача. Решается немного длинно, зато решение очень быстрое.

В формулировке задачи определена возрастающая последовательность 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

БЛОГ НА HUSL

нужно сократить время выполнения

Ответы (2 шт):