Разбор задачи №16

Канал авторов: телеграм (кликабельно)

Текст задачи:

Python 3.9 +

Первым делом импортируем функцию-декоратор "cache" из модуля functools. Она позволяет запоминать и повторно использовать некоторые вызовы для рекусивных функции, значительно ускоряя их выполнение.

from functools import cache

Опишем функцию для поиска делителей числа, все равно пригодится в основной функции f.
Лучший способ искать делители числа - искать их до корня, находя к каждому делителю из "левой" границы соответсвующий правый делитель.
Так, например, для числа 6 в "левой" части найдутся делители: 1, 2
А "правая" найдется по нехитрой формуле: n/i, где n - искомое число 6, а i - итый делитель. Список "правой" части таков: 3 (6/2), 6 (6/1)
Чтобы исключить повторения делителей для чисел, которые являются квадратами, удобно использовать множество. В этой структуре данных элементы не повторяются.

def divizors(n):
    res = {1,}
    sqr = int(n**0.5) #корень числа
    for i in range(2, sqr+1): #правая граница включена
        res.add(i)
        res.add(n//i)
    return res #возвращается неотсортированный set

Важно отметить, что я не включаю само число в состав делителей и не сортирую полученное множество, потому что этого требует условие задания.

Теперь можно заняться написанием и самой функции из задания:

@cache
def f(n):
    if n == 1: return 1
    return sum(map(f, divizors(n)))

Ничего интересного, исключая вызов функции-декоратора, используя @-нотацию, и последней строки. Остановимся на ней подробнее:

sum(map(f, divizors(n)))

Фактически мы ищем все делители числа n, затем с помощью функции map применяем функцию f ко всем делителям и суммируем полученный результат.

Вполне можно было бы переписать вот так:

s = 0
for d in divizors(n):
    s += f(d)
return s

Или так:

sum(f(d) for d in divizors(n)))

Итоговый код:

from functools import cache
def divizors(n):
    res = {1,}
    sqr = int(n**0.5)
    for i in range(2, sqr+1):
        res.add(i)
        res.add(n//i)
    return res
@cache
def f(n):
    if n == 1: return 1
    return sum(map(f, divizors(n)))
print(f(50000000))

Python 3 +

Для более низких версий языка "cache" легко заменяется на "lru_cache(None)". Параметр передаваемый в декораторе говорит о "глубине" запоминания. Максимальное значение задается при None.

from functools import lru_cache
def divizors(n):
    res = {1,}
    sqr = int(n**0.5)
    for i in range(2, sqr+1):
        res.add(i)
        res.add(n//i)
    return res
@lru_cache(None)
def f(n):
    if n == 1: return 1
    return sum(map(f, divizors(n)))
print(f(50000000))

На этом разбор окончен. Советую глубже понять моменты с поиском делителей и работой lru_cache, это может пригодиться в задачах 25 и 19-21 соответственно.

Канал авторов: телеграм