Найти остаток от деления 2^(27^17) на 55.
Просьба доходчиво объяснить решение.
(A ≡ B mod C) ⇔ (A*A ≡ A*B mod C)
т.е.
x^y mod z ≡ (((((x mod z) * x) mod z) * x) mod z).....(y раз)... * x) mod z)
анадогично со степенями
(A ≡ B mod C) ⇔ (A^D ≡ (B mod C)^D mod C)
основываясь на этом
вот код
number = 2
power = 27
ppower = 17
root = 55
# (number**(power**ppower)) % root
rest=number
for i in 1..ppower
rest = (rest**power) % root
end
return rest
ответ 18
Оцени ответ
Подпишись на наш канал в телеграм. Там мы даём ещё больше полезной информации для школьников!
