Найти последнюю цифру a ^ b для больших чисел

Опубликовано: 20 Января, 2022

Вам даны два целых числа: основание a (количество цифр d, такое, что 1 <= d <= 1000) и индекс b (0 <= b <= 922 * 10 ^ 15). Вам нужно найти последнюю цифру a ^ b.
Примеры:

 Ввод: 3 10
Выход: 9

Ввод: 6 2
Выход: 6

Ввод: 150 53
Выход: 0

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

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

 Номер | Последние цифры, повторяющиеся в цикле
  1 | 1
  2 | 4, 8, 6, 2
  3 | 9, 7, 1, 3
  4 | 6, 4
  5 | 5
  6 | 6
  7 | 9, 3, 1, 7
  8 | 4, 2, 6, 8
  9 | 1, 9

Из приведенной таблицы видно, что максимальная длина повторения цикла равна 4.
Пример: 2 * 2 = 4 * 2 = 8 * 2 = 16 * 2 = 32 последняя цифра в 32 равна 2, что означает, что после 4-кратного умножения цифра повторяется. Так что алгоритм очень простой.
Источник: Brilliants.org
Алгоритм:

  1. Поскольку числа очень большие, мы храним их в виде строки.
  2. Возьмите последнюю цифру в базе a.
  3. Теперь вычислите b% 4. Здесь b очень большое.
    • Если b% 4 == 0, это означает, что b полностью делится на 4, поэтому наша экспонента теперь будет exp = 4, потому что, умножая число 4 раза, мы получаем последнюю цифру в соответствии с таблицей циклов на диаграмме выше.
    • Если b% 4! = 0, это означает, что b не полностью делится на 4, поэтому наша экспонента теперь будет exp = b% 4, потому что, умножая числовую экспоненту раз, мы получаем последнюю цифру в соответствии с таблицей циклов на диаграмме выше.
    • Теперь вычислите ldigit = pow (last_digit_in_base, exp).
    • Последняя цифра a ^ b будет ldigit% 10.

Ниже представлена реализация описанного выше алгоритма.

Выход :

 3

Автор статьи - Шашанк Мишра (Гуллу). Эта статья рецензируется командой geeksforgeeks.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ