Как найти результат (2^n)% p?

Question

Я застрял в вопросе, который попросил найти (2^n)% p, где n - очень большое число порядка 10^36, а p - простое. Как это сделать быстро? Здесь^означает мощность я наткнулся на этот алгоритм, но он дает переполнение стека в 10^36 очень большой

double power(double a,double b,int mod) 
{ 
if (b==0) 
return 1; 
else if(b%2==0) 
return square(power(a,b/2,mod))%mod; 
else return power(a,b-1,mod)%mod; 
} 

является ли их любым другим способом или улучшение на это ??

Answer 1

В этом случае Python может вам помочь. В python вам не нужно заботиться о диапазоне типа данных, вы просто даете значение данных python автоматически настраивает тип данных переменных.

Answer 2

Вы можете использовать подход разделения и покорения.

Вот основная идея:

2^8 = (2^4)^2 2^4 = (2^2)^2

Таким образом, вы должны были бы вычислить 2^2 раз и квадрат, чтобы получить 2^4. Тогда Квадрат приведет к получению 2^8 и так далее.

Показанный случай отлично работает, если n является степенью 2. Однако, возможно, разбить любые силы, подобные этому, на две или три подзадачи.

Например, если n = 20, оно нарушится до (2^10)^2. , если n = 21, он сломается до (2^10)^2 * 2.

Следовательно, в зависимости от нечетного и четного значения мощности вы можете растворить его в компоненте.

Надеюсь, что иллюстрация была ясна.