Нахождение найти a^s mod b

Question

Нам даны 3 числа: a, s и b, каждый из которых варьируется в диапазоне от 1 до 1000000. Нам нужно найти pow (a, s)% b. Очевидно, мы не можем использовать простую функцию pow, потому что мы не смогли создать большое число, такое как 1000000 . Это решение проблемы:

sol=1 
for(int i=0;i<s;i++) 
{ 
      sol = sol * a; 
      sol = sol % b; 
} 

print sol 

Я не понимаю этот алгоритм. Может кто-нибудь объяснить это мне?

P.S. Где можно найти больше алгоритмов для решения нетривиальных математических задач, таких как этот? Приветствия!

Answer 1

Прежде всего, алгоритм, который вы написали, совсем не оптимизирован, поскольку он линейный по s, в то время как вы можете легко написать журнал (ы) один, как вы можете прочитать here.

Тем не менее, существует не так много, чтобы объяснить: вы просто должны знать, что

a*b mod N = ((a mod N) * (b mod N)) mod N 

и

a^s = a*a*...*a s times 

и сразу следует, что ваш алгоритм вычисляет результат в наивных путь.

Answer 2

^сек мод Ь = (а; • ^с-1) мод б = (мод) • б (а ^с-1 мод б) по модулю Ь = ...

Как вы можете видеть, первый шаг тривиален, а второй шаг - известное свойство по модулю. Таким образом, вы можете повторить и найти ^s mod b.

Как вы упомянули, вы можете сделать лучше. Для другого метода вы можете перейти на Wikipedia. Но я объясню идею этого алгоритма: Представляют число s в двоичной системе, так что вы можете написать s следующим образом:

s = ∑ (2 ^я • б _я), где каждый б _я является 0 или 1.

Итак: а ^сек мод б = а ^{∑ (2 я • б _я)} мод б, так что вы можете просто сделать КН умножения en LSB = 1, затем сдвиг вправо экспонента ...