Каков наилучший способ найти ** b% c (мощность b по модулю c), если c намного меньше b?

Я уже пробовал modPow() Функция для BigInteger в java.
Но это было слишком долго.Каков наилучший способ найти ** b% c (мощность b по модулю c), если c намного меньше b?

Я знаю модульное умножение, даже возведение в степень тоже.

Но я не могу решить эту проблему из-за ограничений.

a, b имеют значения, которые могут иметь 1000000 цифр в нем (настолько огромный, не так ли?). Сейчас я хочу найти (a**b)%c. В качестве первого шага, мы можем сделать a = a % c. Но вот, даже b настолько огромен.

c = 10^9+7

источник

2015-02-02 Bhavesh Munot

Не знаете, что такое TLE в этом контексте? –

libgmp имеет модульную функцию экспоненты, 'mpz_powm' –

Стандартный алгоритм модульного возведения в степень может обрабатывать миллионные показатели без особых трудностей. Это, конечно, не самая медленная вещь, которую вы будете делать с 'b'. – Sneftel

Попробуйте использовать эту функцию. Он использует какой-то JS-движок для вычисления чего-либо. Поместите выражение как параметр String и запустите его.

источник

2015-02-03 09:31:57 roeygol

Простите, но это просто слишком чертовски медленно. Поэтому, даже если это когда-нибудь принесет результат, это слишком поздно. – Deduplicator

Хорошо, но сделал ли это решение, в котором вы нуждались? – roeygol

** Мне это не нужно. И прямой алгоритм слишком медленный в соответствии с OP. Посмотрите на комментарии, я намекнул на правильное решение. Вы можете использовать все это. – Deduplicator

Каков наилучший способ найти ** b% c (мощность b по модулю c), если c намного меньше b?

ответ

Смежные вопросы