16.01 Одна функция

Рекурсивное решение

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление. Функция реализует быстрое возведение в степень (бинарный алгоритм): ; если нечётно, то ; если x чётно, то . Требуется вычислить сумму на промежутке : для каждого считаем через рекурсивную функцию и накапливаем сумму, в конце берём остаток по модулю .

def f(a, x):
    # База:
    if x == 1:
        return a
    # Нечётная степень: a ** x = a * (a ** (x-1))
    if x % 2 != 0:
        return a * f(a, x - 1)
    # Чётная степень: a ** x = (a ** (x/2))**2
    b = f(a, x // 2)
    return b * b

ans = 0
# Суммируем i ** i для i от 2 до 10000
for i in range(2, 10000 + 1):
    ans += f(i, i)

# Выводим сумму по модулю 10000
print(ans % 10000)