Last Digit of A ^ B
Submit solution
Points:
100 (partial)
Time limit:
2.0s
Memory limit:
64M
Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, Swift, VB
Nestor is doing his math homework, a subject in which he has had many operations that did in the past three days and is very tired. The task is that given two numbers A and B are want to find the last digit of . You must help Nestor with this task. Will be given two numbers: the base
and the index
. You will find the last digit of the result of
.
Input specification
The first line of the entry contains a number T, the number of test cases. T lines follow. For each test case, a line with A and B separated by a space.
Output specification
For each test case should print a line with the result.
Sample input
2
3 10
6 2
Sample output
9
6
Comments
.
Con recursión es más fácil, pero consume mucha memoria. Debe existir alguna manera de optimizarlo en cuanto a esto.
Waho. Aniervs, muchas gracias por tu ayuda.
Pueden darme una pista acerca de cómo resolver este ejercicio.
El problema se puede refrasear como calcular
; eso es lo mismo que
. Ahora que tenemos
, fácilmente (con fuerza bruta o a lápiz y papel) podemos sacar el ciclo de las potencias de cada número menor que 10, y con eso puedes calcular cualquier potencia rápidamente, por ejemplo: si
, entonces las potencias de
lucen:
, y así sucesivamente.
Por otro lado, puedes usar un algoritmo básico llamado potenciación rápida. Sabemos que:
![\displaystyle a^0 = 1](/static/blank.b44917055649.gif)
Con esa formulación recursiva puedes calcular
a partir de
; por tanto luego de
pasos hallas el resultado. Tener en cuenta que las operaciones aritméticas deben ser realizadas módulo
.