long long fast_exp(long long int base,long long int exp,int p) {
int res=1;
while(exp>0) {
if(exp%2==1)
{res=(res*base)%p;}
exp=exp>>1;
base=(base*base)%p;
}
return res;
}
Это функция модульного возведения в степень. Я хочу спросить об этом в то время как цикл. Когда этот цикл заканчивается? Так как exp
всегда больше 0. Я также не понимаю этот цикл в том, как он работает и как он работает построчно. Я не понимаю подход этого цикла.
Сначала вы должны отформатировать код или он плохо читается.
long long fast_exp(long long int base, long long int exp, int p) {
int res = 1;
while (exp > 0) {
if (exp % 2 == 1) {
res = (res * base) % p;
}
exp = exp >> 1; // Note
base = (base * base) % p;
}
return res;
}
Обратите внимание на строку с комментарием. exp
вправо сдвигается на 1 на каждой итерации цикла, так что в конечном итоге он достигает нуля, завершая цикл.
Я думаю Википедия объясняет этот алгоритм хорошо, поэтому мне не нужно его повторять. Псевдокод, который показывает Википедия, почти такой же, как ваш код. Просто сравните их построчно.
Здесь также есть несколько ошибок:
int p
, который должен был быть long long p
int res
, который должен был быть long long res
Других решений пока нет …