Вы пытаетесь вычислить (a^b)%n
или a^(b%n)
?
Если вы хотите первый, то ваш код работает только тогда, когда b является четным числом из-за этого b / 2. «if b%n==1
» неверно, потому что здесь вас не интересует b%n
, а скорее b%2
.
Если вы хотите второй, тогда цикл ошибочен, потому что вы зацикливание b / 2 раза вместо (b% n) / 2 раза.
В любом случае ваша функция излишне сложна. Почему вы зацикливаете до b / 2 и пытаетесь умножить на 2 a каждый раз? Почему бы не просто петли до b и mulitply в один раз каждый раз. Это устранит много ненужной сложности и, таким образом, устранит потенциальные ошибки. Вы думаете, что быстрее сделаете программу быстрее, сократив количество циклов в два раза? Честно говоря, это плохая практика программирования: микро-оптимизация. Это не очень помогает: вы все еще умножаетесь на одно и то же количество раз, все, что вы делаете, сокращается на количество раз, проверяя цикл. Если b обычно мал (например, одна или две цифры), это не стоит проблем. Если b велико - если оно может быть в миллионах - тогда этого недостаточно, вам нужна гораздо более радикальная оптимизация.
Также, почему %n
каждый раз через цикл? Почему бы просто не сделать это один раз в конце?