Задача к ЕГЭ по информатике на тему «одна функция» №3

Просмотров 7 Комментарии 0

Существует алгоритм, позволяющий возводить число $a$ в степень $x$ не за $N$ операций, а за $log2(N )$ . Он называется бинарным алгоритмом возведения в степень.

Алгоритм вычисления значения функции $F (a,x)$ , где $a,x$ — натуральные числа, задан следующими соотношениями:

$F (a,1) = a$

$F (a,x) = a⋅F(a,x − 1)$ , если $x$ нечетное

$F (a,x) = F(a,x∕∕2)⋅F(a,x∕∕2)$ , если $x$ четное

Чему равно значение выражения $(F(2,2)+ F(3,3)+ ...+ F(10000,10000))%10000$ ?

def f(a, x):
    if x == 1:
        return a
    if x % 2 != 0:
        return a * f(a, x - 1)
    b = f(a, x // 2)
    return b * b


ans = 0
for i in range(2, 10000 + 1):
    ans += f(i, i)
print(ans % 10000)

Ответ: 4499