Ссылка на проблему: https://www.hackerearth.com/problem/algorithm/rhezo-and-big-power/description/ Я видел лучшее представление, в котором человек вычислял A%M (так же, как мы делаем на бумаге), и B%(M-1 ); затем эти два пришли в диапазоне целых чисел, и он сделал логарифмический (n) подход, чтобы найти m ^ n% M? Я действительно не могу понять, зачем ему делать B%(M-1).
Вычисление (A pow B) mod M для очень больших A и B (хранится в строке)
comment
Как ему удалось хранить такую большую стоимость Б.
- person Bipul Kumar schedule 26.02.2021
Ответы (1)
Согласно малой теореме Ферма,
a^(p-1) mod p = 1, When p is prime.
Исходя из этого, что касается проблемы, M простое, мы можем выразить A ^ B mod M следующим образом:
A^B mod M = ( A^(M-1) * A^(M-1) *.......* A^(M-1) * A^(x) ) mod M
Где x is B mod M-1 and A ^ (M-1) continues B/(M-1) times
Теперь, из Маленькой теоремы Ферма, A ^ (M-1) mod M = 1.
Следовательно,
A^B mod M = ( 1 * 1 * ....... * 1 * A^(x) ) mod M
Вот почему мы модифицируем B с M-1.
person
MD. MOSHIUR RAHMAN
schedule
27.03.2018
