Нужно посчитать выражение вида (a^b mod c). ^ - степень. Потенциально значение

Question

Нужно посчитать выражение вида (a^b mod c). ^ - степень. Потенциально значение

a^b может быть слишком большим для "влезания" в какой-то тип, да и втупую считать не хочется.
Что можно придумать, чтобы эффективно это посчитать?

#c #embedded #programming #russian

0

01.12.2017

4 ответов

19 просмотров

Roman Hakh

https://habrahabr.ru/post/124258/

0

01.12.2017

Egor Suvorov

Если все числа положительные и нет переполнений, то (a * b % c) == (a % c * b % c) % c. Можно этим пользоваться и перемножать в 64-битном типе, а потом брать по модулю (если он 32-битный).

0

01.12.2017

Egor Suvorov

А если степень большая, то http://e-maxx.ru/algo/binary_pow

0

01.12.2017

Roman Hakh · Accepted Answer

Roman Hakh

я знаю

0

01.12.2017

170 похожих чатов

Нужно посчитать выражение вида (a^b mod c). ^ - степень. Потенциально значение

4 ответов

Похожие вопросы