Ещё одна задача на длинную арифметику (или нет). Читаем условие:
Понятно, что десять тысяч в десятитысячной степени - это очень большое число, которые не помещается в стандартные типы данных. Всё это, конечно, не относится к Python, поэтому давайте попробуем решить задачу в лоб.
Считываем входные два числа и преобразовываем их к числовому типу:
И можно попробовать сразу вывести ответ:
Здесь мы возводим одно число в степень и берём остаток от деления на 10, тем самым оставляя последнюю цифру. И, на удивление, решение задачи просто влетает.
На этом месте можно было бы просто закончить разбор задачи и приступить к другой. Но хочется рассказать пару дополнений, которые позволять решать такие задачи на других языках программирования или с ещё большими ограничениями.
Во-первых, можно заметить, что при перемножении двух произвольных чисел, последняя цифра результата зависит только от последних цифр множителей. А это значит, что от числа a нам нужна лишь последняя цифра:
После этого возведение числа a в степень b будет сильно быстрее. Но результат всё ещё не будет помещаться в стандартные типы данных (максимум = 9^10000).
Следующим шагом можно внимательнее посмотреть, какими получаются последнии цифры при возведении в степень:
- 2^1 = 2, 2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32 (снова 2 в конце)
- 3^1 = 3, 3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243 (снова 3 в конце)
Если проделать такое упражнение для всех цифр, то можно заметить, что ответы всегда идут по кругу. Для многих цифр длина круга равна 4, для некоторых (например четвёрки) - 2, а для нуля, пятёрки и шестёрки - 1.
Получается, чтобы узнать последнюю цифру, не надо возводить в большую степень, а надо лишь посмотреть, какому значению на круге она соответствует. Это легко сделать с помощью остатка на деление:
Здесь мы не разделяем цифры на разные длины круга, а берём общую для всех - 4. Небольшая сложность, что степени идут с 1, а не с 0. Поэтому мы сначала вычитаем единицу, а в самом конце её добавляем.
После этого максимум, который надо будет вычислять - это 9^4, что, очевидно, помещается в стандартные типы данных. Более того, даже без первого улучшения, 10000^4 тоже вмещается в int64.
Предыдущий выпуск: Задача 863. Антиарифметическая перестановка
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.