Найти последнюю цифру a ^ b для больших чисел
Вам даны два целых числа: основание 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
Алгоритм:
- Поскольку числа очень большие, мы храним их в виде строки.
- Возьмите последнюю цифру в базе a.
- Теперь вычислите 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 и многому другому, см. Полный курс подготовки к собеседованию .