Самый эффективный способ найти последнюю цифру a^b

Question

Я новичок в питоне. Я ищу вычислить (a ** b) % 10 наиболее эффективным способом (то есть упрощение силовой части). Я нашел один способ сделать это: ((a % 10) ** b) % 10, У меня вопрос, есть ли более эффективные способы сделать это? Эта проблема является расширением задачи CodeFights. Первоначальная проблема принята (a ** b) % 10,

Answer 1

• Поскольку числа mod 10 образуют кольцо, вы можете вычислить остаток mod 10 при каждом промежуточном значении, не влияя на результат.

• E сть O(log b) пошаговый алгоритм под названием Square-and-multiply, который может значительно ускорить ваши вычисления.

  Основная идея заключается в том, что даже b мы можем просто возвести в квадрат аргумент и разделить показатель степени на 2 без изменения результата. Для странных b Извлекаем одну силу a (или наш текущий аргумент) и действуйте как в четном случае (возведение в квадрат и деление пополам).

Таким образом, если вы реализуете алгоритм квадрата и умножения и вычисляете мод вычетов 10 после каждого шага, у вас будет хороший и эффективный способ вычислить вашу последнюю цифру.

Answer 2

• Шаг 1: Возьмите входы a и b как строку символов
• шаг 2:
  • преобразуйте только последний символ в целое число и сохраните в переменной скажем m.
  • преобразуйте только два последних символа b в целое число и сохраните в переменной, скажем, n. Если b - один символ, то конвертируйте только этот символ.
• Шаг 3: найти х. if n % 4 == 0: x = 4 else: x = n % 4
• шаг 4: last_digit = (m ** x) % 10

Краткое объяснение: Если вы перечислите начальные расширения степени, вы найдете шаблон. Таким образом, мы можем уменьшить a и b до m и x соответственно. Потому что речь идет о последней цифре.

Вы можете посетить: этот сайт для лучшего объяснения, чтобы узнать последнюю цифру ^b