Когда цикл заканчивается в программе, потому что он всегда имеет положительное значение?

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. Я также не понимаю этот цикл в том, как он работает и как он работает построчно. Я не понимаю подход этого цикла.

-5

Решение

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

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
1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector