Задача #2421
Количество программ
(М. Шагитов, П. Хаматов) У исполнителя Калькулятор имеются две команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить сумму всех делителей
Первая команда увеличивает число на 1, вторая – увеличивает число на сумму всех его натуральных делителей (включая 1 и само число). Сколько существует программ, для которых при исходном числе 2 результатом является число 62?
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
207
def sumdiv(n):
return sum(i for i in range(1, n + 1)
if n % i == 0)
def F(start, end):
return 1 if start == end else \
0 if start > end else \
F(start + 1, end) + F(start + sumdiv(start), end)
print(F(2, 62))
# ------------------------------------
# Автор: М. Шагитов
lst = [0] * 300
lst[2] = 1
for i in range(2, 62):
lst[i + 1] += lst[i]
lst[i + sumdiv(i)] += lst[i]
print(lst[62])